WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Задача обчислення виразів - Реферат

Задача обчислення виразів - Реферат

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

 
 

Цікаве