UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75838
останнє поновлення: 2016-12-03
за 7 днів додано 10

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваЗадача обчислення виразів (реферат)
Автор
РозділІнформатика, компютерні науки
ФорматWord Doc
Тип документуРеферат
Продивилось3134
Скачало173
Опис
ЗАКАЧКА
Замовити оригінальну роботу

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

 

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

 

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

 

Числовий вираз – це запис, складений за певними правилами зі сталих,

імен, знаків операцій та дужок. Сталі та імена у виразі позначають

операнди, а знаки операцій з дужками задають послідовність операцій,

виконання яких породжує значення виразу. У цьому розділі ми займемося

питанням, як за виразом відтворити виконання операцій та обчислити його

значення.

 

Зробимо деякі уточнення. Будемо вважати, що структура виразів і правила

вилучення зайвих дужок відповідають означенням із підрозділу 2.2.4.

Вирази містять:

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

не уточнюючи поки що, звідки саме.

 

Існує кілька способів представити послідовність операцій, задану

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

записом. Саме ним ми і скористаємося.

 

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

 

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

 

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

 

Звичною формою виразів є інфіксна, коли знак бінарної операції

записується між позначеннями операндів цієї операції, наприклад, a+b.

Розглянемо запис знаків операцій після позначень операндів, тобто

постфіксний запис, наприклад, ab+. Такий запис має також назву

зворотного польського, оскільки його запропонував польський логік Ян

Лукасевич. Далі словосполучення "зворотний польський запис"

позначатимемо ЗПЗ.

 

Опишемо відповідність між звичними інфіксними виразами та їх ЗПЗ. Нехай

E, E1, E2 позначають вирази в інфіксній формі, , – знаки

унарної та бінарної операцій, – ім'я функції. Виразу E залежно від

його вигляду відповідає ЗПЗ L(E) згідно з правилами:

 

E L(E)

 

стала чи ім'я змінної E

 

'(' E1 ')' L(E1)

 

E1 L(E1)

 

E1E2 L(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. Алгоритм побудови ЗПЗ.

 

Вираз є послідовністю символів – цифр, букв та інших знаків. Але вони

утворюють лексичні одиниці, або лексеми, чотирьох різновидів: сталі,

імена (позначення функцій), знаки операцій та дужки. Будемо дивитися на

вираз саме як на послідовність лексем, які ми одержуємо послідовним

читанням виразу зліва направо.

-----> Page:

0 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ