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

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

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

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

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

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

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

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

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

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

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

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