1.2. Представление арифметических выражений в польской записи

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

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

Рассмотрим два выражения в инфиксной форме: а + b  c и (a + b)  c, а также соответствующие им постфиксные формы: abc+ и ab+c. В каждом случае порядок следования операндов в этих формах совпадает с порядком следования операндов в исходных выра­жениях. При просмотре выражения a + b  c первый операнд a может быть сразу же помещен в постфиксное выражение. Очевидно, что оператор "+" нельзя записать в это выражение до тех пор, пока туда не будет помещен второй, еще не просмотренный операнд b. Следовательно, оператор "+" необходимо сохранить в стеке, а впос­ледствии извлечь оттуда и записать в соответствующую позицию строки польской записи. После просмотра операнда b этот символ записывается непосредственно за операндом a. К этому моменту просмотрены уже два операнда. Однако оператор "+" еще нельзя разместить в строке польской записи, так как за ним следует опе­ратор "", имеющий более высокий приоритет. Во втором выраже­нии наличие скобок обеспечивает выполнение операции "+" в первую очередь.

Таким образом, если рассматриваемый оператор имеет больший приоритет, чем оператор в вершине стека, то этот новый оператор также записывается в стек. Значит при окончательной выборке из стека всех элементов и записи их в строку постфиксной формы этот новый оператор будет предшествовать оператору, рас­положенному в стеке под ним. Это является правильным с учетом приоритетов операторов. С другой стороны, если приоритет нового оператора меньший, чем у оператора в стеке, то оператор из верши­ны стека должен быть выполнен первым. Он извлекается из стека и помещается в выходную строку, а рассматриваемый оператор сравнивается со следующим элементом, занимающим теперь вершину стека, и т.д.

Помещая во входную строку сноски, можно изменить последова­тель­ность вычислений. Так, при обнаружении левой скобки она всег­да записывается в стек. Когда встречается соответствующая ей пра­вая скобка, все операторы между этими скобками переписываются из стека в выходную строку, так как они должны быть выполнены преж­де любых других операторов, расположенных за этими скобками. При этом открывающаяся скобка также должна быть удалена из стека. Обе скобки (левая и правая) не помещаются затем ни в строку поль­ской записи, ни в стек.