Математическая логика и теория алгоритмов. Стенюшкина В.А. - 107 стр.

      a) выберем число 2 и сохраним его в стеке:
      ├ * ( 3 + ,
        ≺    ≺ ≺     ≻ ;
      б) аналогично удалим 3 из выражения и поместим в стек:
      ├ * ( + 4 ),
         ≺ ≺ ≺      ≺    ≻ ;
      в) с 4 поступим подобным образом:

       ├ * ( + ),
         ≺ ≺      ≺   ≻ ;
       г) выполним сложение двух верхних элементов в стеке и результат оста-
вим там же; удалим символ +:
       ├ * ( ),
        ≺ ≺ ≈;
       д) отбросим скобки:
       ├ * ┤,
          ≺ ≻ ;
       е) произведём умножение двух верхних элементов стека, оставляя ре-
зультат в стеке; удалим символ *:
       ├ ┤;
       ж) останов; ответ находится в стеке.

      6.12 Представление промежуточной программы

       Промежуточная программа представляет собой линейную запись синта-
ксического дерева программы, легко транслируемую в магнитный код. основ-
ными терминальными символами промежуточной программы являются опера-
торы и операнды. Операторы представляются внутри компилятора числовыми
кодами, а операнды – указателями на соответствующие таблицы и идентифика-
торов. Одной из форм представления промежуточной программы является
постфиксная польская запись, которая (в отличие от инфиксной) указывает по-
рядок выполнения операций. Например арифметическое выражение а+b*c в
постфиксной польской записи будет выглядеть как аbc*+d+. Расшифровка в
постфиксной польской записи выглядит очень просто: выражение просматри-
вается слева направо, и его элементы помещаются в стек. Если очередной эле-
мент – знак операции, то (в случае двухместной операции) два верхних элемен-
та извлекаются из стека, над ними выполняется операция и результат помещае-
тся в стек; операция удаляется из входной строки, просмотр продолжается. В
постфиксной польской записи можно представить также все операторы исход-
ной программы. Например, условный оператор if <выражение> then <опера-
тор1> else <оператор2> будет иметь вид: <выражение> <метка1> BZ <опера-
тор1> <метка2> BR <метка1> <оператор2> <метка2>. Здесь BZ – бинарная опе-
рация, которая осуществляет переход на <метка1>, если значение <выражение>