Пример реализации
Пусть задано выражение a+b*c+(d*e+f)*g. Необходимо записать это выражение в постфиксной форме. Правильным ответом будет выражение abc*+de*f+g*+. Решаем эту задачу, используя стек.
Пусть исходная информация хранится в строке S=”a+b*c+(d*e+f)*g”. Результат будем получать в строке В.
Начинаем последовательно просматривать символы исходной строки, причем стек пуст и В – пустая строка.
Букву «a» помещается в строку В, а операцию «+» помещаем в стек. Букву «b» помещаем в строку В. На этот момент стек и строка В выглядят следующим образом:
В = ”ab” | |
+ |
Операцию «*» помещаем в стек, т.к. элемент в вершине стека имеет более низкий приоритет. Букву «с» помещаем в строку В, после чего имеем
В = ”abс” | |
* | |
+ |
Следующий символ строки S «+». Анализируем стек и видим, что элемент в вершине стека «*» и следующий за ним «+» имеют приоритеты не ниже текущего, следовательно, обе операции извлекаем из стека и помещаем в строку В, а текущий элемент помещаем в стек. В итоге имеем
В = ”abс*+” | |
+ |
Далее в строке S следует символ «(», его помещаем в стек, а букву «d» помещаем в строку В, в результате получается
В = ”abс*+d” | |
( | |
+ |
Следующий в строке S символ «*». Так как открывающую скобку нельзя извлечь из стека до тех пор, пока не встретилась закрывающая, то «*» помещаем в стек. Букву «e» помещаем в строку В:
В = ”abс*+de” | |
* | |
( | |
+ |
Следующий прочитанный символ «+», и т.к. элемент стека «*» имеет более высокий приоритет, то извлекаем его из стека и помещаем в строку В, а текущий символ «+» помещаем в стек. Символ «f» помещаем в строку В:
В = ”abс*+de*f” | |
+ | |
( | |
+ |
Далее в строке S идет закрывающая скобка, все элементы стека до символа «)» помещаем в строку В (это элемент «+»), а сам символ «(» извлекаем из стека. Обе скобки игнорируются:
В = ”abс*+de*f+” | |
+ |
Операцию «*» помещаем в стек, а букву «g» – в строку В:
В = ”abс*+de*f+g” | |
* | |
+ |
Все символы строки S рассмотрены, следовательно, анализируем состояние стека, если он не пуст, то переписываем все его элементы в строку В:
В = ”abс*+de*f+g*+” |
Таким образом, просмотрев исходную информацию только один раз, мы решили поставленную задачу.
Текст программы, реализующий рассмотренный алгоритм, может иметь следующий вид:
. . .
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;
}
Дата добавления: 2014-12-30; просмотров: 879;