ОБЧИСЛЕННЯ ВИРАЗІВ
У ПРОГРАМУВАННІ
1. Задача обчислення виразів
Числовий вираз – це запис, складений за певними правилами зі сталих, імен, знаків операцій та дужок. Сталі та імена у виразі позначають операнди, а знаки операцій з дужками задають послідовність операцій, виконання яких породжує значення виразу. У цьому розділі ми займемося питанням, як за виразом відтворити виконання операцій та обчислити його значення.
Зробимо деякі уточнення. Будемо вважати, що структура виразів і правила вилучення зайвих дужок відповідають означенням із підрозділу 2.2.4. Вирази містять:
- цілі й дійсні сталі та імена змінних;
- символи "+", "-", "*", "/" двомісних арифметичних операцій;
- імена (ідентифікатори) одномісних функцій sin та cos;
- дужки "(" та ")".
Задачу обчислення значення виразу розіб'ємо на дві підзадачі:
1) прочитати вираз і побудувати його внутрішнє подання;
2) за внутрішнім поданням виразу обчислити його значення.
Для початку будемо вважати, що вирази читаються з "зовнішнього світу", не уточнюючи поки що, звідки саме.
Існує кілька способів представити послідовність операцій, задану виразом. Один із них – це подання виразу його зворотним польським записом. Саме ним ми і скористаємося.
2. Зворотний польський запис
та алгоритм його побудови
2.1. Зворотний польський запис.
Звичною формою виразів є інфіксна, коли знак бінарної операції записується між позначеннями операндів цієї операції, наприклад, a+b. Розглянемо запис знаків операцій після позначень операндів, тобто постфіксний запис, наприклад, ab+. Такий запис має також назву зворотного польського, оскільки його запропонував польський логік Ян Лукасевич. Далі словосполучення "зворотний польський запис" позначатимемо ЗПЗ.
Опишемо відповідність між звичними інфіксними виразами та їх ЗПЗ. Нехай E, E1, E2 позначають вирази в інфіксній формі, <op1>, <op2> – знаки унарної та бінарної операцій, <opf> – ім'я функції. Виразу E залежно від його вигляду відповідає ЗПЗ L(E) згідно з правилами:
| E | L(E) |
| стала чи ім'я змінної | E |
| '(' E1')' | L(E1) |
| <op1>E1 | L(E1) <op1> |
| E1<op2>E2 | L(E1) L(E2) <op2> |
| <opf>'('E1')' | L(E1) <opf> |
Як бачимо, ці правила рекурсивні, і ЗПЗ складніших виразів описуються за допомогою ЗПЗ їх простіших підвиразів.
У наступних прикладах покажемо застосування наведених правил з урахуванням старшинства та властивості лівостороннього зв'язування операцій :
L( b * c ) = bc * ;
L( -(-a) ) = L( (-a)) - = a--;
L( a + b * c ) = L(a) L(b*c) + = abc * + ;
L( a + b - c ) = L( a + b ) L( c ) - = ab + c - ;
L( 1-sin( a+b ) ) = L(1) L( sin( a+b ) ) - = 1 L( a+b ) sin - =1 ab + sin - .
Вирази зі знаками унарних операцій далі не розглядаються.
2.2. Алгоритм побудови ЗПЗ.
Вираз є послідовністю символів – цифр, букв та інших знаків. Але вони утворюють лексичні одиниці, або лексеми, чотирьох різновидів: сталі, імена (позначення функцій), знаки операцій та дужки. Будемо дивитися на вираз саме як на послідовність лексем, які ми одержуємо послідовним читанням виразу зліва направо.
Розглянемо докладніше побудову вихідної послідовності лексем L(E) за лексемами виразу E.
З правил побудови L(E) випливає, що порядок елементарних позначень операндів (сталих чи імен змінних) у виразах E і L(E) однаковий, тому сталі й імена змінних можна одразу записувати у вихідну послідовність.
Порядок знаків операцій змінюється: у вхідному виразі вигляду E1 op2E2 знак op2 передує знакам операцій виразу E2, а у вихідному виразі L(E1) L(E2) op2 – навпаки. Тому знак op2 треба запам'ятати, видати L(E2), а після нього – op2. Знаки операцій у виразах E1 та E2 потрібно так само зберігати й видавати після ЗПЗ виразів, що позначають операнди цих операцій. Таке змінювання порядку знаків досягається за використання магазина, або стека; знаки операцій надходять у нього й вилучаються у вихідний вираз за принципом "останнім увійшов – першим вийшов" ("Last In – First Out", або LIFO).
На порядок знаків у вихідному виразі впливає їх старшинство, або пріоритет:
L( a + b * c ) = abc * + ; L( a + b - c ) = ab + c - .
Операція '*' старша за '+', тому в першому виразі операція '+' застосовується до значень a та b*c. У другому виразі старшинство '+' та '-' однакове, операції мають властивість лівостороннього зв'язування, тому '+' застосовується до a і b, а '-' – до a+b і c.
Отже, коли у вхідній послідовності читається знак операції op2, з верхівки магазина треба видати у вихідний вираз усі знаки, пріоритети яких не нижчі від пріоритету op2 (усі вони є знаками з виразу E1), і тільки після цього запам'ятати op2 у магазині. Якщо пріоритет знака з верхівки магазина нижче ніж у op2, то op2 записується в магазин, оскільки має появитися у вихідному виразі раніше.
Процес побудови ЗПЗ виразу можна подати послідовністю трійок вигляду
(вихідна послідовність лексем;
магазин;
непрочитана частина виразу).
Верхівку магазина будемо вказувати праворуч.
Приклад 1. Початок перетворення виразу a+b*c зображається послідовністю трійок
( ; ; a + b * c ) – початковий стан: вихідна послідовність і магазин порожні;
( a ; ; + b * c ) – ім'я перенесено у вихідну послідовність;
( a ; + ; b * c ) – знак перенесено в магазин;
( ab ; + ; * c ) – ім'я перенесено у вихідну послідовність.
Після цього знак '*' вміщується в магазин над знаком '+':
( ab ; + * ; c ).
Пріоритет операції '*' вищий від '+', тому b є операндом '*', а не '+'.
При перетворенні виразу a+b-c результатом читання його початку a+b буде
( ab ; + ; - c ),
після чого знак '-' "виштовхне" з магазина '+', тобто наступною буде трійка
( ab + ; - ; c ).
Пріоритети '+' і '-' рівні, тому b пов'язується з операцією '+' ліворуч.-
Відкриваюча та відповідна їй закриваюча дужки задають початок і кінець виразу, всі знаки операцій якого мають з’явитися у вихідному виразі раніше від знаків, що є в магазині перед появою відкриваючої дужки. Для відокремлення цих знаків відкриваюча дужка записується в магазин. За появи на вході закриваючої дужки всі знаки операцій до відкриваючої дужки виштовхуються з магазина у вихідний вираз, а дужка вилучається з магазина, тобто дужки "взаємно знищуються".
Ім'я функції записується в магазин і видається безпосередньо за ЗПЗ виразу її аргумента. Ім'я функції виштовхується з верхівки з появою у вхідному виразі знака операції або закриваючої дужки.
Після того, як вираз прочитано, в магазині ще можуть залишитися знаки операцій; їх треба записати у вихідну послідовність.
Отже, уся описана обробка лексем подається таким алгоритмом:
whileна вході є лексема C do
caseCof
стала чи ім'я змінної: скопіювати її у вихідну послідовність;
знак операції: до появи на верхівці магазину відкриваючої дужки виштовхнути звідти та скопіювати у вихідну послідовність усі знаки, чий пріоритет не нижчий від пріоритету С; заштовхнути С в магазин;
відкриваюча дужка: заштовхнути С в магазин;
закриваюча дужка: до появи на верхівці магазину відкриваючої дужки виштовхнути звідти та скопіювати у вихідну послідовність усі знаки операцій; виштовхнути відкриваючу дужку;
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 ; * -) – перенесено три числа в магазин;