Сторінка
2
магазин;
непрочитана частина виразу). Верхівку магазина будемо вказувати праворуч. Приклад 1. Початок перетворення виразу a+b*c зображається послідовністю трійок ( ; ; a + b * c ) – початковий стан: вихідна послідовність і магазин порожні; ( a ; ; + b * c ) – ім'я перенесено у вихідну послідовність; ( a ; + ; b * c ) – знак перенесено в магазин; ( a b ; + ; * c ) – ім'я перенесено у вихідну послідовність. Після цього знак '*' вміщується в магазин над знаком '+': ( a b ; + * ; c ). Пріоритет операції '*' вищий від '+', тому b є операндом '*', а не '+'. При перетворенні виразу a+b-c результатом читання його початку a+b буде ( a b ; + ; - c ), після чого знак '-' "виштовхне" з магазина '+', тобто наступною буде трійка ( a b + ; - ; c ). Пріоритети '+' і '-' рівні, тому b пов'язується з операцією '+' ліворуч.ç Відкриваюча та відповідна їй закриваюча дужки задають початок і кінець виразу, всі знаки операцій якого мають з’явитися у вихідному виразі раніше від знаків, що є в магазині перед появою відкриваючої дужки. Для відокремлення цих знаків відкриваюча дужка записується в магазин. За появи на вході закриваючої дужки всі знаки операцій до відкриваючої дужки виштовхуються з магазина у вихідний вираз, а дужка вилучається з магазина, тобто дужки "взаємно знищуються". Ім'я функції записується в магазин і видається безпосередньо за ЗПЗ виразу її аргумента. Ім'я функції виштовхується з верхівки з появою у вхідному виразі знака операції або закриваючої дужки. Після того, як вираз прочитано, в магазині ще можуть залишитися знаки операцій; їх треба записати у вихідну послідовність. Отже, уся описана обробка лексем подається таким алгоритмом: 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. ç Уточнимо обробку ЗПЗ таким алгоритмом: while на вході є лексема C do case C of
стала чи ім'я змінної: заштовхнути її значення в магазин;
знак двомісної операції: виштовхнути з магазину два верхні елементи; обчислити результат застосування до них операції зі знаком С та заштовхнути результат в магазин;
знак одномісної операції: виштовхнути з магазину верхній елемент; обчислити результат застосування до нього операції зі знаком С та заштовхнути результат в магазин; end;
видати верхній елемент магазина як результат. Задачі 20.2.* Імітувати процес обчислення ЗПЗ: а) 1 2 3 4 + - *; б) 1 2 3 + 4 - *; в) 1 2 + 3 - 4 *. 20.3. У процесі побудови ЗПЗ, якщо знак операції потрапляє до вихідної послідовності, то її операнди уже перебувають там, і операцію можна застосувати до них. Поміняти алгоритм побудови ЗПЗ так, щоб замість побудови одразу обчислювалося значення початкового виразу. Можна використати два магазини – знаків операцій та операндів.
4. Записи з варіантами. У підрозділах 20.5, 20.6 ми уточнимо у вигляді підпрограм наведені вище алгоритми побудови ЗПЗ та обчислення значення виразу. Там ми скористаємося зручним засобом мови Паскаль, який досі не розглядався, – це записи з варіантами. У нашій задачі ЗПЗ виразу будується у вигляді послідовності лексем. Послідовність можна подати масивом, списком, або файлом. У будь-якому разі це буде послідовність однотипних елементів. Проте у виразах є лексеми чотирьох різновидів: сталі, імена, знаки операцій і дужки. Природно у ЗПЗ зберігати не сталі чи імена змінних, а їх значення. Знаки операцій та дужки є символами, а імена функцій – рядками. Отже, доводиться говорити про кілька різних типів для подання лексем. Але незрозуміло, як різнотипні елементи зібрати в одну послідовність. Одним із розв'язань цієї суперечності є використання записів із варіантами. Подивимося на лексеми як на пари вигляду (різновид, значення). Наприклад, стала 12 подається як (стала, 12), ім'я функції sin – (ім'я, 'sin'), відкриваюча дужка – як (дужка, '('). Для задання множини різновидів лексем означимо тип-перелік Ttlx: type Ttlx = (con, nam, ops, par, err). Ці імена є скороченнями від constant, name, operation sign, parenthesis та error – стала, ім'я, знак операції, дужка та помилка відповідно. Отже, нам потрібен тип пар, першими компонентами яких є типи лексем, тобто елементи з переліку Ttlx, а другими – значення відповідних типів. У мові Паскаль для подання пар природно скористатися структурними типами, яких нам потрібно 5, разом із типом для помилкових лексем. Об'єднати різні типи структур в один можна за допомогою означення типу структур (записів) із варіантами. Вираз, що задає тип таких записів, схожий на вирази, якими задаються типи записів, або структур. Його загальний вигляд такий: record
Завантажити реферат