|
|||||||||||||||||||||||||||||||||||||||||||||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Пример реализацииПусть задано выражение a + b * c +(d * e + f)* g. Необходимо записать это выражение в постфиксной форме. Правильным ответом будет выражение abc *+ de * f + g *+. Решаем эту задачу, используя стек. Пусть исходная информация хранится в строке S =” a + b * c +(d * e + f)* g ”. Результат будем получать в строке В. Начинаем последовательно просматривать символы исходной строки, причем стек пуст и В – пустая строка. Букву «a» помещается в строку В, а операцию «+» помещаем в стек. Букву «b» помещаем в строку В. На этот момент стек и строка В выглядят следующим образом:
Операцию «*» помещаем в стек, т.к. элемент в вершине стека имеет более низкий приоритет. Букву «с» помещаем в строку В, после чего имеем
Следующий символ строки S «+». Анализируем стек и видим, что элемент в вершине стека «*» и следующий за ним «+» имеют приоритеты не ниже текущего, следовательно, обе операции извлекаем из стека и помещаем в строку В, а текущий элемент помещаем в стек. В итоге имеем
Далее в строке S следует символ «(», его помещаем в стек, а букву «d» помещаем в строку В, в результате получается
Следующий в строке S символ «*». Так как открывающую скобку нельзя извлечь из стека до тех пор, пока не встретилась закрывающая, то «*» помещаем в стек. Букву «e» помещаем в строку В:
Следующий прочитанный символ «+», и т.к. элемент стека «*» имеет более высокий приоритет, то извлекаем его из стека и помещаем в строку В, а текущий символ «+» помещаем в стек. Символ «f» помещаем в строку В:
Далее в строке S идет закрывающая скобка, все элементы стека до символа «)» помещаем в строку В (это элемент «+»), а сам символ «(» извлекаем из стека. Обе скобки игнорируются:
Операцию «*» помещаем в стек, а букву «g» – в строку В:
Все символы строки S рассмотрены, следовательно, анализируем состояние стека, если он не пуст, то переписываем все его элементы в строку В:
Таким образом, просмотрев исходную информацию только один раз, мы решили поставленную задачу. Текст программы, реализующий рассмотренный алгоритм, может иметь следующий вид: ... struct Stack { char c; // Символ операции Stack *Next; }; int Prior (char); Stack* InS(Stack*,char); Stack* OutS(Stack*,char*); void main () { Stack *t, *Op = NULL; // Стек операций Op – пуст char a, In[50], Out[50]; // Входная In и выходная Out строки int k = 0, l = 0; // Текущие индексы для строк puts(" Input formula: "); gets(In); while (In[k]!= '\0') { // Анализируем символы строки In // Если символ «)», выталкиваем из стека в выходную строку все операции if (In[k] == ')') { while ((Op -> c)!= '(') { // до открывающей скобки Op = OutS(Op,&a); // Считываем элемент из стека if (!Op) a = '\0'; Out[l++] = a; // и записываем в строку Out. } t = Op; // Удаляем из стека открывающую скобку Op = Op -> Next; free(t); } // Если символ строки In – буква, заносим ее в строку Out if (In[k] >= 'a' && In[k] <= 'z') Out[l++] = In[k]; // Если символ – открывающая скобка, записываем ее в стек if (In[k] == '(') Op = InS(Op,In[k]); /* Если символ – знак операции, переписываем из стека в строку Out все операции с большим или равным приоритетом */ if (In[k] == '+' || In[k] == '–' || In[k] == '*' || In[k] == '/') { while (Op!= NULL && Prior (Op -> c) >= Prior (In[k])) { Op = OutS(Op,&a); // Извлекаем из стека символ Out[l++] = a; // и записываем в строку Out } Op = InS(Op,In[k]); // Текущий символ – в стек } k++; } // Конец цикла анализа входной строки // Если стек не пуст, переписываем все операции в выходную строку while (Op!=NULL) { Op = OutS(Op,&a); Out[l++] = a; } Out[l] = '\0’; printf("\n Polish = %s", Out); // Выводим на экран результат } //======= Функция реализации приоритета операций ========= int Prior (char a) { switch (a) { case '*': case '/': return 3; case '–': case '+': return 2; case '(': return 1; } return 0; } // ============== Добавление элемента в стек ============= Stack* InS(Stack *t, char s) { Stack *t1 = (Stack*) malloc(sizeof(Stack)); t1 -> c = s; t1-> Next = t; return t1; } // ============== Извлечение элемента из стека =============== Stack* OutS(Stack *t, char *s) { Stack *t1 = t; *s = t -> c; t = t->Next; free(t1); return t; } Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.008 сек.) |