Обчислення иразів у програмуванні

ОБЧИСЛЕННЯ ВИРАЗІВ

У ПРОГРАМУВАННІ

1. Задача обчислення виразів

Числовий вираз – це запис, складений за певними правилами зі сталих, імен, знаків операцій та дужок. Сталі та імена у виразі позначають операнди, а знаки операцій з дужками задають послідовність операцій, виконання яких породжує значення виразу. У цьому розділі ми займемося питанням, як за виразом відтворити виконання операцій та обчислити його значення.

Зробимо деякі уточнення. Будемо вважати, що структура виразів і правила вилучення зайвих дужок відповідають означенням із підрозділу 2.2.4. Вирази містять:

- цілі й дійсні сталі та імена змінних;

- символи "+", "-", "*", "/" двомісних арифметичних операцій;

- імена (ідентифікатори) одномісних функцій sin та cos;

- дужки "(" та ")".

Задачу обчислення значення виразу розіб'ємо на дві підзадачі:

1) прочитати вираз і побудувати його внутрішнє подання;

2) за внутрішнім поданням виразу обчислити його значення.

Для початку будемо вважати, що вирази читаються з "зовнішнього світу", не уточнюючи поки що, звідки саме.

Існує кілька способів представити послідовність операцій, задану виразом. Один із них – це подання виразу його зворотним польським записом. Саме ним ми і скористаємося.

2. Зворотний польський запис

та алгоритм його побудови

2.1. Зворотний польський запис.

Звичною формою виразів є інфіксна , коли знак бінарної операції записується між позначеннями операндів цієї операції, наприклад, a +b . Розглянемо запис знаків операцій після позначень операндів , тобто постфіксний запис , наприклад, ab +. Такий запис має також назву зворотного польського , оскільки його запропонував польський логік Ян Лукасевич. Далі словосполучення "зворотний польський запис" позначатимемо ЗПЗ.

Опишемо відповідність між звичними інфіксними виразами та їх ЗПЗ. Нехай E , E₁ , E₂ позначають вирази в інфіксній формі, <op₁ >, <op₂ > – знаки унарної та бінарної операцій, <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 ) = 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 ) однаковий, тому сталі й імена змінних можна одразу записувати у вихідну послідовність.

Порядок знаків операцій змінюється: у вхідному виразі вигляду E ₁ op₂ E ₂ знак op₂ передує знакам операцій виразу E ₂ , а у вихідному виразі L (E ₁ ) L (E ₂ ) op₂ – навпаки. Тому знак op₂ треба запам'ятати, видати L (E ₂ ), а після нього – op₂ . Знаки операцій у виразах E <

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать