ОБЧИСЛЕННЯ ВИРАЗІВ У ПРОГРАМУВАННІ

E1E2L(E1) L(E2)

'('E1')'L(E1)

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

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

L( b * c ) = b c * ;

L( -(-a) ) = L( (-a)) - = a--;

L( a + b * c ) = L(a) L(b*c) + = a b c * + ;

L( a + b - c ) = L( a + b ) L( c ) - = a b + c - ;

L( 1-sin( a+b ) ) = L(1) L( sin( a+b ) ) - = 1 L( a+b ) sin - =1 a b + sin - .

Вирази зі знаками унарних операцій далі не розглядаються.

2.2. Алгоритм побудови ЗПЗ.

Вираз є послідовністю символів – цифр, букв та інших знаків. Але вони утворюють лексичні одиниці, або лексеми, чотирьох різновидів: сталі, імена (позначення функцій), знаки операцій та дужки. Будемо дивитися на вираз саме як на послідовність лексем, які ми одержуємо послідовним читанням виразу зліва направо.

Розглянемо докладніше побудову вихідної послідовності лексем L(E) за лексемами виразу E.

З правил побудови L(E) випливає, що порядок елементарних позначень операндів (сталих чи імен змінних) у виразах E і L(E) однаковий, тому сталі й імена змінних можна одразу записувати у вихідну послідовність.

Порядок знаків операцій змінюється: у вхідному виразі вигляду E1 op2 E2 знак op2 передує знакам операцій виразу E2, а у вихідному виразі L(E1) L(E2) op2 – навпаки. Тому знак op2 треба запам'ятати, видати L(E2), а після нього – op2. Знаки операцій у виразах E1 та E2 потрібно так само зберігати й видавати після ЗПЗ виразів, що позначають операнди цих операцій. Таке змінювання порядку знаків досягається за використання магазина, або стека; знаки операцій надходять у нього й вилучаються у вихідний вираз за принципом "останнім увійшов – першим вийшов" ("Last In – First Out", або LIFO).

На порядок знаків у вихідному виразі впливає їх старшинство, або пріоритет:

L( a + b * c ) = a b c * + ; L( a + b - c ) = a b + c - .

Операція '*' старша за '+', тому в першому виразі операція '+' застосовується до значень a та b*c. У другому виразі старшинство '+' та '-' однакове, операції мають властивість лівостороннього зв'язування, тому '+' застосовується до a і b, а '-' – до a+b і c.

Отже, коли у вхідній послідовності читається знак операції op2, з верхівки магазина треба видати у вихідний вираз усі знаки, пріоритети яких не нижчі від пріоритету op2 (усі вони є знаками з виразу E1), і тільки після цього запам'ятати op2 у магазині. Якщо пріоритет знака з верхівки магазина нижче ніж у op2, то op2 записується в магазин, оскільки має появитися у вихідному виразі раніше.

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