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

В предыдущей статье [3] мы научились преобразовывать арифметическое выражение в так называемую “постфиксную” форму. Компилятору такое выражение очень просто оценить (вычислить), в отличие от привычной человеку инфиксной формы. Попробуем научиться вычислять такие выражения. Для этого нам опять пригодится наш стек, без него ничего не получится :).

Итак, пусть дано некоторое постфиксное выражение, состоящее из цифр и знаков четырех арифметических операций, причем знак “/” соответствует целочисленному делению, например, такое: 62+5*84/–. Предполагается, что выражение — допустимое, записанное по всем правилам формирования таких выражений. Для расчета его значения должен использоваться следующий алгоритм:

1. Пока не конец строковой величины — постфиксного выражения, считывать ее символы слева направо:

если очередной символ — цифра,

· то

· · поместить ее в стек;

· иначе (очередной символ —

знак операции)

· · — извлечь два верхних элемента

из стека в переменные х и у;

· · — произвести вычисление:

у <очередной знак операции> х;

· · — поместить результат вычисления

в стек.

все

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

Для размещения элемента в стеке, для извлечения из него элемента и для вывода значения на вершине стека используем соответственно вспомогательные алгоритмы Поместить, Извлечь и Вершина, разработанные в [1]³, а для вычислений — вспомогательные алгоритмы Сложить , Вычесть , Умножить и Разделить , описанные в [2] (напомним, что в них действия выполняются над двумя числами, находящимися в двух “верхних” элементах стека, а результат размещается на его вершине).

Ясно, что в данном случае, как и в [2] и в отличие от [4], стек будем моделировать как массив чисел, т.е. его описание должно быть таким:

цел nmax; nmax := 20;

цел таб стек[1:nmax];

цел верх; верх := 0;

Примечание. Переменная верх — индекс последнего заполненного элемента.

При разработке программы возникает необходимость преобразовать символ-цифру (из постфиксного выражения) в число (для размещения его в стеке). В новой версии системы программирования “КуМир” для операционной системы Windows такое преобразование можно провести с помощью функции лит_в_цел . У нее два аргумента. Первый — преобразуемое литерное или символьное значение, второй — величина логического типа, возвращающая результат в зависимости от успешности проведенного преобразования.

Вся программа решения задачи имеет вид:

алг Вычисление значения постфиксного

выражения

нач лит postfix, цел i, лог успех

· postfix := '62+5*84/-'

· нц для i от 1 до длин(postfix)

· · если postfix[i] >= '0' и postfix[i] <= '9'

· · · то

· · · · Поместить(лит_в_цел(postfix[i], успех));

· · · иначе

· · · · выбор

· · · · · при postfix[i] = '+': Сложить

· · · · · при postfix[i] = '-': Вычесть

· · · · · при postfix[i] = '*': Умножить

· · · · · при postfix[i] = '/': Разделить

· · · · все

· · все

· кц

· вывод нс, "Результат ", Вершина

кон

Если вы все-таки работаете в системе “КуМир” 4.0 для MS-DOS, то для преобразования символов-цифр в число можно использовать функцию цел:

Поместить(цел(postfix[i])

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

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

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

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

Литература

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

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

3. Насыров Н.А. Стек и компьютер. / “В мир информатики” № 132 (“Информатика” № 20/2009).

4. Формирование постфиксного выражения. / “В мир информатики” № 132 (“Информатика”
№ 20/2009).

---

³ Можно также использовать варианты, описанные в [4], в которых, напомним, добавление нового значения в стек и извлечение значения на его вершине проводятся в конце заполненной части массива. — Прим. ред.