Алгоритм, использующий стек

Получение обратной польской записи с использованием стека может осуществляться весьма просто на основе алгоритма, предложенного Дейкстрой, который ввел понятие стекового приоритета операций:

Суть алгоритма в следующем. Просматривается исходная строка символов S слева направо, операнды переписываются в выходную строку В, а знаки операций заносятся в стек, который первоначально пуст, на основе следующих правил:

1) если в строке S встретился операнд, то помещаем его в строку В;

2) если в S встретилась открывающая скобка, то помещаем ее в стек;

3) если в S встретилась закрывающая скобка, то выталкиваем из стека в строку В все операции до открывающей скобки, саму отрывающую скобку также извлекаем из стека; обе скобки (открывающая и закрывающая) игнорируются;

4) если в S встретилась операция Х, то выталкиваем из стека все операции, приоритет которых не ниже Х, после чего операцию Х записываем в стек;

5) при достижении конца строки S, если стек не пуст, переписываем его элементы в выходную строку В.

Обратная польская запись обладает рядом замечательных свойств, которые превращают ее в идеальный промежуточный язык при трансляции.

Во-первых, вычисление выражения, записанного в обратной польской записи, может проводиться путем однократного просмотра, что является весьма удобным при генерации объектного кода программ.

Например, вычисление полученного выражения (15.1) может быть проведено следующим образом:

Здесь R1 и R2 – вспомогательные переменные.

Пример реализации

Пусть задано выражение 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;

}