Головна Головна -> Реферати українською -> Інформатика, комп'ютери, програмування -> Алгоритм обчислення виразу за його ЗПЗ. Записи з варіантами

Алгоритм обчислення виразу за його ЗПЗ. Записи з варіантами

Назва:
Алгоритм обчислення виразу за його ЗПЗ. Записи з варіантами
Тип:
Реферат
Мова:
Українська
Розмiр:
7,46 KB
Завантажень:
25
Оцінка:
 
поточна оцінка 5.0


Скачати цю роботу безкоштовно
Пролистати роботу: 1  2 
Позначення операндів у ЗПЗ передують знакам операцій, які до них застосовуються, тому при читанні ЗПЗ спочатку обчислюються та запам'ятовуються операнди, а потім до них застосовується операція.

ЗПЗ виразу тепер читається, а для обчислень застосовується магазин. Але тепер це вже магазин операндів, а не знаків операцій. Числа, що є значеннями сталих чи змінних, переносяться в магазин. Якщо черговою лексемою є знак двомісної операції, то з магазина вилучаються два верхні елементи, і результат застосування операції до цих значень записується в магазин. За знаку одномісної операції з магазина вилучається лише один елемент. Ім'я функції на вході задає її застосування до елемента з верхівки магазина та вміщення результату в магазин. Після закінчення вхідного списку лексем у магазині зберігається лише одне число – значення всього виразу.

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

(магазин операндів; непрочитана частина ЗПЗ).

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

Приклад 1. Обчислення ЗПЗ "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;

видати верхній елемент магазина як результат.

2. Записи з варіантами.

У підрозділах 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

спільна частина;

варіантна частина

end;

У спільній частині означаються поля, наявні в усіх об'єднуваних типах (їх список може бути порожнім). У варіантній частині після ключового слова case означається селектор – додаткове поле перелічуваного типу. Насправді воно є спільним в усіх об'єднуваних типах. Потім записуються значення селектора разом із відповідними варіантами наборів полів, якими відрізняються об'єднувані типи. Варіантом є список означень полів, записаний у дужках.

Звернімо увагу, що слово end в означенні лише одне – можна вважати, що воно є "закриваючою дужкою", яка відповідає як record, так і case.

Приклад 2. Нехай у виразах імена й помилкові лексеми мають не більше восьми символів, і діють означення типів st8 = string[8] та Ttlx. Тип лексем задається означенням

type Tlx = record { спільна частина порожня }

case stl : Ttlx of

con : (numb : real);

nam : (name : st8 );

ops : (sig : char);

par : (prt : char);

err : (wrlx : st8 )

end

Завантажити цю роботу безкоштовно
Пролистати роботу: 1  2 



Реферат на тему: Алгоритм обчислення виразу за його ЗПЗ. Записи з варіантами

BR.com.ua © 1999-2017 | Реклама на сайті | Умови використання | Зворотній зв'язок