Алгоритм обчислення виразу за його ЗПЗ. Записи з варіантами, Детальна інформація
Алгоритм обчислення виразу за його ЗПЗ. Записи з варіантами
Реферат на тему:
Алгоритм обчислення виразу за його ЗПЗ. Записи з варіантами
1. Алгоритм обчислення виразу за його ЗПЗ
Позначення операндів у ЗПЗ передують знакам операцій, які до них застосовуються, тому при читанні ЗПЗ спочатку обчислюються та запам'ятовуються операнди, а потім до них застосовується операція.
ЗПЗ виразу тепер читається, а для обчислень застосовується магазин. Але тепер це вже магазин операндів, а не знаків операцій. Числа, що є значеннями сталих чи змінних, переносяться в магазин. Якщо черговою лексемою є знак двомісної операції, то з магазина вилучаються два верхні елементи, і результат застосування операції до цих значень записується в магазин. За знаку одномісної операції з магазина вилучається лише один елемент. Ім'я функції на вході задає її застосування до елемента з верхівки магазина та вміщення результату в магазин. Після закінчення вхідного списку лексем у магазині зберігається лише одне число – значення всього виразу.
Процес обчислення можна подати послідовністю пар вигляду
(магазин операндів; непрочитана частина ЗПЗ).
Спочатку магазин порожній, а в кінці в ньому єдине значення.
Приклад 1. Обчислення ЗПЗ "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
Уточнимо обробку ЗПЗ таким алгоритмом:
while на вході є лексема C do
case C of
стала чи ім'я змінної: заштовхнути її значення в магазин;
знак двомісної операції: виштовхнути з магазину два верхні елементи; обчислити результат застосування до них операції зі знаком С та заштовхнути результат в магазин;
знак одномісної операції: виштовхнути з магазину верхній елемент; обчислити результат застосування до нього операції зі знаком С та заштовхнути результат в магазин;
end;
видати верхній елемент магазина як результат.
2. Записи з варіантами.
У підрозділах 20.5, 20.6 ми уточнимо у вигляді підпрограм наведені вище алгоритми побудови ЗПЗ та обчислення значення виразу. Там ми скористаємося зручним засобом мови Паскаль, який досі не розглядався, – це записи з варіантами.
Алгоритм обчислення виразу за його ЗПЗ. Записи з варіантами
1. Алгоритм обчислення виразу за його ЗПЗ
Позначення операндів у ЗПЗ передують знакам операцій, які до них застосовуються, тому при читанні ЗПЗ спочатку обчислюються та запам'ятовуються операнди, а потім до них застосовується операція.
ЗПЗ виразу тепер читається, а для обчислень застосовується магазин. Але тепер це вже магазин операндів, а не знаків операцій. Числа, що є значеннями сталих чи змінних, переносяться в магазин. Якщо черговою лексемою є знак двомісної операції, то з магазина вилучаються два верхні елементи, і результат застосування операції до цих значень записується в магазин. За знаку одномісної операції з магазина вилучається лише один елемент. Ім'я функції на вході задає її застосування до елемента з верхівки магазина та вміщення результату в магазин. Після закінчення вхідного списку лексем у магазині зберігається лише одне число – значення всього виразу.
Процес обчислення можна подати послідовністю пар вигляду
(магазин операндів; непрочитана частина ЗПЗ).
Спочатку магазин порожній, а в кінці в ньому єдине значення.
Приклад 1. Обчислення ЗПЗ "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
Уточнимо обробку ЗПЗ таким алгоритмом:
while на вході є лексема C do
case C of
стала чи ім'я змінної: заштовхнути її значення в магазин;
знак двомісної операції: виштовхнути з магазину два верхні елементи; обчислити результат застосування до них операції зі знаком С та заштовхнути результат в магазин;
знак одномісної операції: виштовхнути з магазину верхній елемент; обчислити результат застосування до нього операції зі знаком С та заштовхнути результат в магазин;
end;
видати верхній елемент магазина як результат.
2. Записи з варіантами.
У підрозділах 20.5, 20.6 ми уточнимо у вигляді підпрограм наведені вище алгоритми побудови ЗПЗ та обчислення значення виразу. Там ми скористаємося зручним засобом мови Паскаль, який досі не розглядався, – це записи з варіантами.
The online video editor trusted by teams to make professional video in
minutes
© Referats, Inc · All rights reserved 2021