Алгоритм обчислення виразу за його ЗПЗ
Позначення операндів у ЗПЗ передують знакам операцій, які до них застосовуються, тому при читанні ЗПЗ спочатку обчислюються та запам'ятовуються операнди, а потім до них застосовується операція.
ЗПЗ виразу тепер читається, а для обчислень застосовується магазин. Але тепер це вже Магазин операндів, а не знаків операцій. Числа, що є значеннями сталих чи змінних, переносяться в магазин. Якщо черговою лексемою є знак двомісної операції, то з магазина вилучаються два верхні елементи, і результат застосування операції до цих значень записується в магазин. За знаку одномісної операції з магазина вилучається лише один елемент. Ім'я функції на вході задає її застосування до елемента з верхівки магазина та вміщення результату в магазин. Після закінчення вхідного списку лексем у магазині зберігається лише одне число – значення всього виразу.
Процес обчислення можна подати послідовністю пар вигляду
Магазин операндів; Непрочитана частина ЗПЗ.
Спочатку магазин порожній, а в кінці в ньому єдине значення.
Приклад 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 – ??? }