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