Обчислення иразів у програмуванні, Детальна інформація

Відкриваюча та відповідна їй закриваюча дужки задають початок і кінець виразу, всі знаки операцій якого мають з’явитися у вихідному виразі раніше від знаків, що є в магазині перед появою відкриваючої дужки. Для відокремлення цих знаків відкриваюча дужка записується в магазин. За появи на вході закриваючої дужки всі знаки операцій до відкриваючої дужки виштовхуються з магазина у вихідний вираз, а дужка вилучається з магазина, тобто дужки "взаємно знищуються".

Ім'я функції записується в магазин і видається безпосередньо за ЗПЗ виразу її аргумента. Ім'я функції виштовхується з верхівки з появою у вхідному виразі знака операції або закриваючої дужки.

Після того, як вираз прочитано, в магазині ще можуть залишитися знаки операцій; їх треба записати у вихідну послідовність.

Отже, уся описана обробка лексем подається таким алгоритмом:

while на вході є лексема C do

case C of

стала чи ім'я змінної: скопіювати її у вихідну послідовність;

знак операції: до появи на верхівці магазину відкриваючої дужки виштовхнути звідти та скопіювати у вихідну послідовність усі знаки, чий пріоритет не нижчий від пріоритету С; заштовхнути С в магазин;

відкриваюча дужка: заштовхнути С в магазин;

закриваюча дужка: до появи на верхівці магазину відкриваючої дужки виштовхнути звідти та скопіювати у вихідну послідовність усі знаки операцій; виштовхнути відкриваючу дужку;

end;

3. Алгоритм обчислення виразу за його ЗПЗ

Позначення операндів у ЗПЗ передують знакам операцій, які до них застосовуються, тому при читанні ЗПЗ спочатку обчислюються та запам'ятовуються операнди, а потім до них застосовується операція.

ЗПЗ виразу тепер читається, а для обчислень застосовується магазин. Але тепер це вже магазин операндів, а не знаків операцій. Числа, що є значеннями сталих чи змінних, переносяться в магазин. Якщо черговою лексемою є знак двомісної операції, то з магазина вилучаються два верхні елементи, і результат застосування операції до цих значень записується в магазин. За знаку одномісної операції з магазина вилучається лише один елемент. Ім'я функції на вході задає її застосування до елемента з верхівки магазина та вміщення результату в магазин. Після закінчення вхідного списку лексем у магазині зберігається лише одне число – значення всього виразу.

Процес обчислення можна подати послідовністю пар вигляду

(магазин операндів; непрочитана частина ЗПЗ).

Спочатку магазин порожній, а в кінці в ньому єдине значення.

Приклад 20.2. Обчислення ЗПЗ "2 3 * 4 +" подається так:

( ; 2 3 4 * - );

( 2 ; 3 4 * - ) – число 2 перенесено в магазин;

( 2 3 ; * 4 -) – те саме з 3;

( 6 ; 4 - ) – до операндів 2 і 3 застосовано множення;

( 6 4 ; - ) – число 4 перенесено в магазин;

(2 ; ) – до операндів 6 і 4 застосовано віднімання.

За обчислення ЗПЗ "2 3 4 * -" утвориться така послідовність:

( ; 2 3 4 * - );

(2 3 4 ; * -) – перенесено три числа в магазин;

(2 12 ; - ) – 3 і 4 перемножено;

(-10 ; ) – від 2 віднято 12. \xF0E7

Уточнимо обробку ЗПЗ таким алгоритмом: