Построение обратной польской записи

Одной из главных причин, лежащих в основе появления языков программирования высокого уровня, явились вычислительные задачи, требующие больших объёмов рутинных вычислений. Поэтому к языкам программирования предъявлялись требования максимального приближения формы записи вычислений к естественному языку математики. В этой связи одной из первых областей системного программирования сформировалось исследование способов трансляции выражений. Здесь получены многочисленные результаты, однако наибольшее распространение получил метод трансляции с помощью обратной польской записи, которую предложил польский математик Я.Лукашевич.

Арифметическое выражение вида:

(A+B)*(C+D)-E

в форме обратной польской записи будет иметь вид:

AB+CD+*E-

Характерные особенности этого выражения состоят в следовании символов операций за символами операндов и в отсутствии скобок.

Обратная польская запись обладает рядом замечательных свойств, которые превращают ее в идеальный промежуточный язык при трансляции. Во-первых, вычисление выражения, записанного в обратной польской записи, может проводиться путем однократного просмотра, что является весьма удобным при генерации объектного кода программ. Во-вторых, получение обратной польской записи из исходного выражения может осуществляться весьма просто на основе простого алгоритма, предложенного Дейкстрой. Для этого вводится понятие стекового приоритета операций (табл. 10.):

Таблица 10.

Операция	Приоритет
(	0
)	1
+ -	2
* /	3

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

а) если стек пуст, то операция из исходной строки переписывается в стек;

б) операция выталкивает из стека все операции с большим или равным приоритетом в выходную строку;

в) если очередной символ из исходной строки есть открывающая скобка, то он проталкивается в стек;

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

Рассмотрим текст программы, выполняющей рассмотренные выше действия.

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

struct st // Описание элемента стека

{ char c;

st *next;

};

st *push(st *,char); // занесение в стек

char pop(st **); // чтение из стека

int PRIOR(char); // возвращает приоритет операции

void main(void)

{

st *OPR=NULL; // стек операций пуст

char in[80],out[80]; // входная и выходная строки

int k,point;

do

{ puts("Введите выражение(в конце '='):");

fflush(stdin);

gets(in); // ввод арифметического выражения

k=point=0;

while(in[k]!='\0' && in[k]!='=') // пока не дойдем до '='

{ if(in[k]==')') // если очередной символ - ')'

{ while((OPR->c)!='(') // то удаляем из стека в

out[point++]=pop(&OPR); // выходную строку все знаки операций

// до открывающей скобки

pop(&OPR); // Удаляем из стека открывающую скобку

}

if(in[k]>='a' && in[k]<='z') // если символ - буква ,то

out[point++]=in[k]; // заносим её в выходную строку

if(in[k]=='(') // если очередной символ - '(' ,то

OPR=push(OPR,'('); // заносим её в стек

if(in[k]=='+' || in[k]=='-' || in[k]=='/' || in[k]=='*')

{ // Если следующий символ - знак операции ,то все на-

// ходящиеся в стеке операции с большим или равным

// приоритетом переписываются в выходную строку

while((OPR!=NULL)&&(PRIOR(OPR->c)>=PRIOR(in[k])))

out[point++]=pop(&OPR);

OPR=push(OPR,in[k]); // запись в стек новой операцию

}

k++; // переход к следующему символу входной строки

}

while(OPR) // после рассмотрения всего выражения

out[point++]=pop(&OPR); // перезапись операции

out[point]='\0'; // из стека в выходную строку

printf("\n%s\n",out); // и печатаем её

fflush(stdin);

puts("\nПовторить(y/n)?");

} while(getch()!='n');

}

// push записывает в стек символ a, возвращает

// указатель на новую вершину стека

st *push(st *head,char a)

{ st *PTR;

if(!(PTR=(st*) malloc(sizeof(*PTR))))

{ puts("Нет памяти"); exit(-1);}

PTR->c=a; //

PTR->next=head; //

return PTR; // PTR -новая вершина стека

}

// pop удаляет символ с вершины стека. Возвращает

// удаляемый символ. Изменяет указатель на вершину стека

char pop(st **head)

{ st *PTR;

char a;

if(!(*head)) return '\0'; //Если стек пуст, возвращаем \0

PTR=*head; // в PTR - адрес вершины стека

a=PTR->c;

*head=PTR->next; // Изменяем адрес вершины стека

free(PTR); // Освобождение памяти

return a; // Возврат символа с вершины стека

}

// Функция PRIOR возвращает приоритет арифм. операции

int PRIOR(char a)

{ switch(a)

{ case '*':case '/':return 3;

case '-':case '+':return 2;

case '(':return 1;

} return 0;

}