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

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

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

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

Магазин операндів; Непрочитана частина ЗПЗ.

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

Приклад 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

Тут stl є ім'ям селектора, а в дужках указано варіанти – списки означень полів, поставлені у відповідність його значенням. Щоправда, тут усі ці списки мають по одному елементу.

Тип селектора задається тільки ім'ям, а імена полів повинні бути унікальними в межах означення типу запису. Синтаксис списку полів варіанта такий самий, як і списку полів запису зокрема, можливі спільна й варіантна частини з таким самим синтаксисом.

Приклад. 3. Означити тип записів для подання таких відомостей про студента: прізвище, ім'я, курс, оцінки останньої сесії, а також рік народження та відношення до військової служби юнаків, або знак Зодіаку та колір очей дівчат.

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

Type Sex=male, female; {тип стать – чоловіча або жіноча}

Type Student=

Record

Surname, name: string[30]; {прізвище та ім'я – рядкові}

Course: integer; marks: string[10]; {курс та оцінки}

Case sexslc: Sex Of

Male: year: integer; military: boolean;

Female: Zodiak: string[10]; eyecolor: string[10]

End

Під варіантні частини зміннихзаписів виділяється стільки пам'яті, скільки її потрібно для найдовшого з варіантів. Так, селектор змінних типу Tlx займає 1 байт, а довжина варіантної частини визначається найдовшим типом st8 9 байтів у Турбо Паскаль. Дані типу Student займають 31+31+1+11+11=85 байтів.

Селектор призначений для відображення типу варіантної частини запису. Але Доступ до ділянок пам'яті варіантної частини запису здійснюється через імена полів незалежно від значення селектора в записі, тобто засоби мови не забезпечують відповідності значень селектора й варіантів у зміннихзаписах. Тому потрібна особлива увага, щоб не робити помилок на зразок наступної:

Var lx: Tlx; a: real;

Lx. stl:= con;

Lx. nam:= 'sin'; { створено невідповідність!!! }

If lx. stl = con Then a:= lx. numb { значення a – ??? }