Формирование постфиксного выражения

vmi@1september.ru

Когда человек хочет передвинуть гору, он начинает с того, что убирает маленькие камни.

В статье “Стек и компьютер” в этом выпуске рассказывается о так называемой “постфиксной” записи арифметического выражения. Ее особенностью является то, что в ней знаки операций указываются после опе­рандов (чисел, над которыми выполняются действия), например, “3 4 +” и “7 9 /”. Вычисление значения выражения в таком виде обладает рядом преимуществ по сравнению с привычной нам “инфиксной записью”, и именно так вычисления проводятся в компьютере.

Разработаем программу, которая переводит выражение в инфиксной записи в постфиксную, причем сделаем это для простого случая — когда в исходном выражении скобок нет. Алгоритм перевода для этого случая описан в указанной статье. Напомним, что в нем используется стек, но его отличие от стека, рассмотренного в [1–2], в том, что в нем хранятся не числа, а знаки операций, т.е. описание массива, моделирующего стек, должно быть таким:

цел nmax; nmax := 10;

сим таб стек[1:nmax];

цел вершина; вершина := 0;

Учтем также тот факт, что программная реализация вспомогательных алгоритмов Поместить (реализует размещение в стеке нового значения) и Извлечь (осуществляет извлечение значения из стека; извлекаемое значение является результатом алгоритма-функции) значительно упрощается, если добавление нового значения в стек и извлечение значения на его вершине проводить в конце заполненной части массива (об этом шла речь в редакционном комментарии к статье [1]). Индекс последнего заполненного элемента (вершины стека) будем хранить в переменной вершина (ее описание приведено выше).

Соответствующие вспомогательные алгоритмы имеют вид:

алг Поместить(арг сим знак)

|Аргумент — знак операции,

|размещаемый в стеке

нач

· вершина := вершина + 1

· стек[вершина] := знак

кон

алг сим Извлечь

нач

· |Значение функции:

· знач := стек[вершина]

· вершина := вершина - 1

кон

Примечание. Контроль границ стека в приведенных алгоритмах не проводится.

В программе нам понадобится сравнивать приоритеты знаков операций (“+”, “–”, “*”, “/”). Примем, что приоритет двух первых знаков равен 1, двух последних — 2, и создадим функцию Приоритет, возвращающую одно из этих значений для соответствующего знака:

алг цел Приоритет(арг сим знак)

нач

· если знак = "+" или знак = "-"

· · то

· · · знач := 1

· · иначе

· · · знач := 2

· все

кон

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

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

алг Получение_постфиксного_выражения

нач лит инфикс, постфикс, цел i, сим знак

· вывод нс, "Введите инфиксное выражение "

· ввод инфикс

· постфикс := ""

· |Исследуем каждый символ

· |инфиксного выражения

· нц для i от 1 до длин(инфикс)

· · |Если i-й символ - цифра

· · если инфикс[i] >= "0" и инфикс[i] <= "9"

· · · то

· · · · |Добавляем его в постфиксную

· · · · |запись

· · · · постфикс := постфикс + инфикс[i]

· · · иначе |i-й символ - знак операции

· · · · |Если стек пуст

· · · · если вершина = 0

· · · · · то |Помещаем этот знак в стек

· · · · · · Поместить(инфикс[i])

· · · · · иначе |Сравниваем приоритеты

· · · · · · · · |операций

· · · · · · если Приоритет(инфикс[i]) >

· · · · · · · · Приоритет(стек[вершина])

· · · · · · · то

· · · · · · · · Поместить(инфикс[i])

· · · · · · · иначе

· · · · · · · · нц пока вершина > 0

· · · · · · · · |Пока стек не пуст

· · · · · · · · · если Приоритет(инфикс[i])

· · · · · · · <= Приоритет(стек[вершина])

· · · · · · · · · · то

· · · · · · · · · · · |Извлекаем знак

· · · · · · · · · · · |с вершины стека

· · · · · · · · · · · знак := Извлечь

· · · · · · · · · · · |и приписываем его

· · · · · · · · |к постфиксному выражению

· · · · · · · · · · · постфикс :=

· · · · · · · · · · · постфикс + знак

· · · · · · · · · все

· · · · · · · · кц

· · · · · · · |Помещаем текущий знак

· · · · · · · |операции в стек

· · · · · · · Поместить(инфикс[i])

· · · · ·  все

· · · · все

· · все

· кц

· |Добавляем оставшиеся знаки операций

· |из стека

· |в постфиксную запись, пока стек

· |не пуст

· нц пока вершина > 0

· · |Извлекаем знак с вершины стека

· · знак := Извлечь

· · |и приписываем его к постфиксному

· · |выражению

· · постфикс := постфикс + знак

· кц

· |Выводим результат

· вывод нс, "Соответствующее постфиксное

· выражение: ", постфикс

кон

Задания для самостоятельной работы

Разработайте варианты приведенной программы, в которых в заданном инфиксном выражении могут быть:

1) пробелы;

2) скобки (алгоритм перевода описан в статье “Стек и компьютер” в этом выпуске).

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

Литература

1. Насыров Н.А. Стек — первое знакомство. / “В мир информатики” № 129 (“Информатика” № 17/2009).

2. Насыров Н.А. Учим стек вычислять. / “В мир информатики” № 130 (“Информатика” № 18/2009).