Лекция 8.

Обратная польская запись. Трансляция правильных формул в программу для стекового калькулятора.

Обратная польская запись

Обратная польская запись, или постфиксная нотация, или обратная польская нотация (ОПН) — это форма записи математических выражений, в которой операнды расположены перед знаками операций.

Пример 1. Выражение 2*3-4 в обратной польской записи выглядит как «2 3 * 4 -», а выражение 2+3*(8-7/2) - как «2 3 8 7 2 / - * +»

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

Трансляция правильных формул в программу для стекового калькулятора.

Как преобразовать правильную формулу в польскую запись?

Разработаем транслятор правильных формул в программу для стекового калькулятора.

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

Пример 2. Выражение вида (a+b)*c соответствует следующей программе для Стекового калькулятора:

СК.Начать работу

Стек операций.Добавить '(' в стек

СК.Добавить 'a' в стек

Стек операций. Добавить '+' в стек

СК.Добавить 'b' в стек

СК.Сложить ('+' и '(' удаляются из стека операндов)

Стек операций.Добавить '*' в стек

СК.Добавить 'c' в стек

СК.Умножить ('*' удаляется из стека операндов)

СК.Показать результат

СК.Кончить работу

Замечание. Все формулы берем в дополнительные кругые скобки. Добавленная таким образом правая скобка «заставит» все отложенные операции из стека операции выполниться

Технология программирования сверху вниз (еще бывает снизу вверх)

Компилятор — на базе структур данных: стек (операций), последовательность (символов) P, Справки

Исполнитель Компилятор правильных формул.

Предписание. Компилировать правильную формулу

Стек операций. Начать работу

Обработать символ <вх: '('>

P.Встать в начало последовательности

Цикл для каждого c из непрочитанной части P выполнять

обработать символ <вх: c>

Конец цикла

Обработать символ <вх: ')'>

Утверждение. Стек операций пуст

Стек операций. Кончить работу

Конец предписания

Предписание Обработать символ <вх: с: символ>

вид ::= Справки.вид символа<вх: c: символ>

Выбор

при вид == имя => печатать <”СК.добавить <”, c, “> в стек»>

при вид == левая скобка => стек операций.добавить <c>

при вид == знак =>

Обработать отложенные операции <вх: c>

Утверждение. Стек операций.вершина == “(”

Стек операций.удалить вершину стека

при вид == правая скобка =>

Обработать отложенные операции <вх: c>

Утверждение. Стек операций.вершина == '('

Стек операций. Удалить вершину стека

Конец выбора

Конец предписания

Предписание Обработать отложенные операции <вх: c: символ>

Цикл пока Справки.<Стек операций вершина> выполнима до <вх: c> выполнять

Стек операций. Взять элемент из стека в <вых: x>

Выбор

при x == “+” => печатать («СК.сложить»)

при x == “-” => печатать («СК.вычесть»)

при x == “*” => печатать («СК.умножить»)

при x == “/” => печатать («СК.разделить»)

иначе => отказ

Конец выбора

Конец цикла

Конец предписания

Конец исполнителя

Исполнитель Справки

Предписание Вид символа <вх: c: символ>: вид

Выбор

при с == «+» или с == «-» или с == «*» или с == «/»

=> ответ := знак

при с == '(' => ответ := левая скобка

при с == ')' => ответ := правая скобка

при «a» <= c <= “z” => ответ := имя

иначе => отказ

Конец выбора

Конец предписания

Предписание <вх: с1: символ> выполнима до <вх: c2>: да/нет

Выбор

При вид символа <c1> == левая скобка => ответ := нет

При вид символа <c2> == правая скобка => ответ := да

Иначе => ответ := (вес(с1) >= вес(с2)

Конец выбора

Конец предписания

Предписание вес <вх: с: символ>: 1..2

Выбор

При c == “+” => ответ 1

При c == “-” => ответ 1

При c == “*” => ответ 2

При c == “/” => ответ 2

Конец выбора

Конец исполнителя

А теперь попробуем сделать то же самое, пользуясь компилятором компиляторов YACC: разработаем транслятор инфиксной (общепринятой) записи правильных формул в постфиксную и использовать результат как программу для нашего стекового калькулятора, описанного на лекции 6.

Оказывается, синтаксический анализатор-вычислитель формул, описанный на прошлой лекции, после небольшой переделки превращается в транслятор из инфиксной формы в постфиксную (приведена только начальная, существенная часть программы, находящейся по указанной ссылке):

%token NAME
%left '+' '-'
%left '*' '/'

%%
s : e
  ;
e : e '+' e { printf("+\n"); }
  | e '-' e { printf("-\n"); }
  | e '*' e { printf("*\n"); }
  | e '/' e { printf("/\n"); }
  | '(' e ')'
  | NAME { printf("%d\n", $1); }
  ;
%%
...

Вопрос. Как в YACC-программе заданы приоритеты операций +, -, *, /, то есть как YACC узнает, что, например, * выполняется вперед сложения.

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

%left '+' '-'
%left '*' '/'

Нам осталось только проверить, как работает наш транслятор:

$ yacc InfixToPostfix.y
$ gcc y.tab.c
$ ./a.out | tee output
1-2*(3-7*2)-8/2
1
2
3
7
2
*
-
*
-
8
2
/
-
$ ../StackCalc/StackCalc < output
Stack Calculator commands:
        <number>        Push to stack
        +, -, *, /, %   Ariphmetic operations
        =               Display the stack top
        pop             Remove the stack top
        dup             Duplicate the stack top
        exch            Exchange two elements at the stack top
        show            Show the stack
        clear           Erase the stack
        quit            End the program
= 14
= -11
= -22
= 23
= 4
= 19
$

Если Вы выполните указанные выше действия, то увидите, что формула “1-2*(3-7*2)-8/2” транслировалась нашей YACC-программой в польскую запись «1 2 3 7 2 * - * - 8 2 / -» (Правда, вместо пробелов мы выводим концы строк для удобства подачи формулы в стековый калькулятор).

Результат работы нашей YACC-программы выводится не только на экран, но и в файл output благодаря использованию возможностей Линукса, а именно директивы «| tee», которая направляет стандартный вывод также и в указанный после нее файл.

Теперь, если подать файл output, содержащий полученную польскую запись нашей формулы, на вход стековому калькулятору StackCalc, то мы увидим, что стековый калькулятор успешно вычислил значение выражения: 19.

Подача файла на вход стекового калькулятора («< output») направляет содержимое файла в стандартный ввод и таким образом имитирует ввод чисел с клавиатуры.

Задача для самостоятельного решения: добавить в программу InfixToPostfix.y обработку отрицательных чисел (например, обрабатывать -3+2).

Литература

1. Кушниренко А.Г., Лебедев Г.В. Программирование для математиков: Учеб. пособие для вузов — М.: Наука. Гл.ред.физ.-мат.лит., 1988, с.162-165