(2 12 ; - ) – 3 і 4 перемножено;
(-10 ; ) – від 2 віднято 12. -
Уточнимо обробку ЗПЗ таким алгоритмом:
whileна вході є лексема C do
caseCof
стала чи ім'я змінної: заштовхнути її значення в магазин;
знак двомісної операції: виштовхнути з магазину два верхні елементи; обчислити результат застосування до них операції зі знаком С та заштовхнути результат в магазин;
знак одномісної операції: виштовхнути з магазину верхній елемент; обчислити результат застосування до нього операції зі знаком С та заштовхнути результат в магазин;
end;
видати верхній елемент магазина як результат.
Задачі
20.2.* Імітувати процес обчислення ЗПЗ:
а) 1 2 3 4 + - *; б) 1 2 3 + 4 - *; в) 1 2 + 3 - 4 *.
20.3. У процесі побудови ЗПЗ, якщо знак операції потрапляє до вихідної послідовності, то її операнди уже перебувають там, і операцію можна застосувати до них. Поміняти алгоритм побудови ЗПЗ так, щоб замість побудови одразу обчислювалося значення початкового виразу. Можна використати два магазини – знаків операцій та операндів.
4. Записи з варіантами.
У підрозділах 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.
Приклад 3. Нехай у виразах імена й помилкові лексеми мають не більше восьми символів, і діють означення типів 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 є ім'ям селектора, а в дужках указано варіанти – списки означень полів, поставлені у відповідність його значенням. Щоправда, тут усі ці списки мають по одному елементу.
Тип селектора задається тільки ім'ям, а імена полів повинні бути унікальними в межах означення типу запису. Синтаксис списку полів варіанта такий самий, як і списку полів запису (зокрема, можливі спільна й варіантна частини з таким самим синтаксисом).
Приклад. Означити тип записів для подання таких відомостей про студента: прізвище, ім'я, курс, оцінки останньої сесії, а також рік народження та відношення до військової служби юнаків, або знак Зодіаку та колір очей дівчат.
Зберемо означення спільних даних для юнаків та дівчат у спільну частину означення, а селектор статі та означення відповідних полів – у варіантну:
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 – ??? }
5. Програма обчислення виразів
Програма буде розроблятися із застосуванням так званого методу послідовних уточнень – коли задача розбивається на підзадачі, розв'язання яких перекладається на підпрограми. Програма розв'язання задачі має досить просту структуру та містить виклики цих підпрограм. Далі розробляються підпрограми для розв'язання підзадач, у яких виділяються свої підзадачі. Для їх розв'язання розробляються відповідні підпрограми тощо.
Таким чином, програма та її складові частини не записуються одразу, а розробляються послідовним їх уточненням. У процесі розробки можливі повернення до підпрограм, розроблених раніше, та їх уточнення. Зауважимо, що в цьому процесі окремі частини програми можуть розроблятися одночасно різними програмістами.
Алгоритм обчислення значення виразу в його інфіксній формі уточнимо програмою, у тіло якої запишемо лише виклики двох підпрограм. Перша з них уточнює алгоритм побудови ЗПЗ, друга – алгоритм обчислення значення за ЗПЗ.
В обох алгоритмах неважко виділити операції, які виконуються над послідовністю та магазином лексем – додавання елементів, їх вилучення тощо. Нехай усі ці операції разом із необхідними означеннями, зокрема, типу послідовності лексем Sqlx, зібрано в модулі Sllx. Використання цього модуля укажемо в програмі, а його розробка залишається вправою.
Крім модуля Sllx, у програмі використовується модуль Glx. У ньому мають міститится всі означення, необхідні для читання виразу "з зовнішнього світу". Це читання буде здійснюватися багаторазовим викликом підпрограми getlx читання чергової лексеми виразу. Розробку цього модуля представлено в підр. 20.9–20.10.
Побудову ЗПЗ оформимо функцією ipllx, з якої повертається значення true, якщо в процесі читання виразу не було якихось помилок, і false у противному разі. Побудована послідовність запам'ятовується в змінній Llx. Значення виразу обчислюється за виконання виклику функції llxval і друкується. Отже, програма має вигляд:
program calcul ( input, output );
uses Glx, Sllx;
var Llx : Sqlx;
function ipllx … end;
function llxval … end;
begin
if ipllx( Llx )
then writeln( llxval( Llx ) )
end.
Розробка функцій ipllx і llxval розкривається в наступних двох підрозділах.
20.6. Уточнення алгоритму побудови ЗПЗ
Напишемо функцію ipllx читання та побудови ЗПЗ виразу, з якої повертається ознака відсутності помилок у виразі. Зробимо уточнення постановки задачі: будемо вважати, що вхідні вирази не містять імен змінних, аелементарними позначеннями операндів є лише числові сталі.
Читання чергової лексеми виразу задається функцією getlx із модуля Glx, в якому також означено типи Tlx і Ttlx лексем та їхніх різновидів.
Вважатимемо, що модуль Sllx містить усе необхідне для роботи з послідовністю та магазином лексем, які подаються змінними типів Sqlx і Stlx відповідно. Ініціалізація порожніх послідовності та магазина задається процедурами із заголовками відповідно
procedure initl( var Llx : Sqlx );
procedure inits( var Slx : Stlx );
запис лексеми в магазин – процедурою із заголовком
procedure push( var Slx : Stlx; lx : Tlx );
вилучення лексеми з магазина та повернення її типу – функцією
function pop( var Slx : Stlx; var lx : Tlx) : Ttlx;
добування лексеми з верхівки магазина без вилучення та повернення її типу – функцією
function gett(Slx : Stlx; var lx : Tlx ) : Ttlx;
додавання лексеми в кінець списку –
procedure put( var Llx : Sqlx; lx : Tlx ).
Крім того, функція prior задає обчислення пріоритетів лексем.
Читання чергової лексеми задається в модулі Glx функцією getlx, заголовок якої
function getlx(var lx : Tlx) : boolean;
з її виклику повертається ознака наявності чергової лексеми та сама лексема за допомогою параметра-змінної.
Розроблювана функція ipllx матиме одну особливість. Після того, як вираз прочитано, в магазині ще можуть залишитися знаки операцій; за алгоритмом вони записуються у вихідну послідовність. У цій функції весь вхідний вираз штучно "береться в дужки". Перед його читанням у магазин записується відкриваюча дужка, що відмічає його дно. В кінці магазин лексем обробляється так, ніби на вході з'явилася закриваюча дужка, тобто всі знаки до відкриваючої дужки виштовхуються та копіюються у вихідну послідовність.