asyan.org
добавить свой файл
1 2
Київський національний університет

імені Т.Г. Шевченка

Звіт
З лабораторної роботи № 6

З курсу програмування
Калькулятор ”


Виконав:

Ратушний Тарас

Студент першого курсу

факультету кібернетики

групи К-12

Перевірив: Коваль Ю. В.

Київ

22.04.2008

Зміст



  1. Постановка задачі

  2. Аналіз умови

  3. Проектування програми. Опис модулів

  1. Текст програми

5. Тестування програми

1. Постановка задачі
Необхідно написати програму, яка являє собою вдосконалену модель калькулятора. Калькулятор повинен мати командний інтерфейс з набором стандартних команд, за допомогою яких виконується керування програмою. Калькулятор повинен використовувати процедури, за допомогою яких вираз розкладається на лексеми та будувати бінарне дерево для ведення обрахунків. Крім того, калькулятор має бути доповнений певними функціями, такими як, наприклад, обчислення виразів у різних системах числення та обрахування довгих виразів. Також у ньому має бути реалізована пам'ять, у яку заносяться значення виразів та можуть бути там збережені до наступного виклику програми.

^ 2.Аналіз умови
Програма працює в консольному режимі.

Її цикл роботи складається з введення команди користувача, її розшифрування і виконання.


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

Обчислення подамо у вигляді БНФ:

::=<+->;

::=<*/>;

::=<^>;

::=│’(‘’)’│[‘=’];

::=“Id’{'0-9'};

Для обчислення виразу необхідно побудувати бінарне дерево обчислень у вигляді записів. Даний запис матиме два вказівника на ліве та праве піддерево, дужки обчислюватимуться як окреме дерево, у вузлах дерева зберігатиметься знак операції.

Для побудови бінарного дерева ми розбиваємо вираз на лексеми. Перелік лексем, що використовуються у програмі:

  1. input – змінити вхідну систему числення.

  2. output – змінити систему числення для виводу.

Обидві ці команди можуть мати такі параметри

    1. binary

    2. quo

    3. octal

    4. decimal

    5. hexadecimal

  1. exit, quit – завершує роботу програми.

  2. sleep – завершує
    роботу програми, але зберігає стан програми.

  3. help – виводить довідку для роботи з програмою.

  4. read – виконує зовнішній файл.

  5. write – записує в файл послідовність виразів.

  6. cls – очистка екрану.

  7. крім того користувач вводить вирази, які можуть складатися з таких лексем:

    1. константа в будь-якій системі числення.

    2. ідентифікатор змінної, яким може бути будь-яка послідовність латинських букв, цифр і знаку підкреслювання. На першій позиції не може стояти цифра.

    3. Знак операції

      1. +,-,*

      2. / - цілочисельне ділення, як бінарний оператор, і видалення змінної, як унарний оператор.

      3. **, ^, піднесення до степеня

      4. (,) – круглі дужки.

      5. \ - знак переносу на наступний рядок.

      6. = оператор присвоєння.

Програма обробляє цілі числа як рядки. В різних системах числення.
Всі команди пишуться маленькими латинськими літерами, при цьому синтаксичний аналізатор чутливий до регістру. Деякі команди можна писати скорочено.
Коректність вхідних даних врахована у програмі, тому вони можуть бути будь-якими. Привведенні некоректної лексеми отримується «bl», при неправильному символі у виразі замінюємо його на «ne» відповідно до операції.

Програма повинна реагувати на неправильне введення даних наступним чином: те, що програма може зрозуміти – лишається. Інше викидається і підставляється нейтральний елемент.

Для реалізації пам’яті використовуємо список у вигляді записів. Запис складається з виразу, занесеного в дану комірку пам’яті та вказівник на наступний рядок.

Для обрахування довгих виразів числові константи ми подаємо у вигляді послідовності цифр. Для додавання та віднімання довгих чисел використовуємо процедури, алгоритм роботи яких аналогічний до додавання та віднімання в стовпчик. Для множення довгих чисел використовуємо процедуру з використанням алгоритму множення в стовпчик та процедури додавання довгих чисел. Ділення довгих чисел проводимо методом бінарного пошуку: використовуючи межі max та min результату ділення, на кожному кроці ми знаходимо середнє арифметичне чисел min та max – sa та за допомогою процедури множення знаходимо, у яком уз выдрізків [min, sa], [sa, max] знаходиться ділене і зменшуємо межі max і min. Так до тих пір, поки значення (max-min) не стане рівним 1, що означає, що min і буде шуканою різницею. Операцію піднесення до степеня реалізовуємо через повторення операції множення.


^ 3.Проектування програми. Опис модулів.

Схема будови калькулятора:


Модуль bufio.pas

Даний модуль реалізовує роботу з введенням та виводом інформації.

Він містить три підпрограми:

  1. procedure readbuf; вона зчитує з клавіатури послідовність символів, яка закінчується натисненням кнопки «ввід». Якщо останній символ був «\» то введення продовжується з наступного рядка. Після її виклику в змінній buffer:string зберігається значення введених рядків, а змінна bp:integer стає рівною 1. Тобто показує на початок буфера. Таким чином все готове щоб видавати символи. Перед зчитуванням вона видає запит «>», який означає, що програма готова ввести перший рядок. Запит «>>» означає, що вводиться наступний рядок, який буде приклеєний до попереднього.

  2. function getch:char видає черговий символ з буферу, при цьому курсор bp зміщується до наступного символа. Якщо символів більше нема, то функція повертає значення константи eol.

  3. procedure ungetch; Повертає курсор на символ назад.


^ Модуль longnum.pas

Цей модуль містить цікаву реалізацію роботи з довгою арифметикою. Числа представляються рядками, і всі дії виконуються над рядками, в шістнадцятковій системі числення, бо в ній запис кожного числа коротший, і відповідно всі дії виконуються трохи швидше.

Основна функція function applyoperation(a,b:string; op:char; syst:integer):string;. Вона видає результат операції op яка задається в вигляді символу +,-,*,/,%,^. (Синтаксис ** не використовується). Обидва числа a,b задаються в системі syst яка може приймати значення 2,4,8,10,16. Якщо якесь число не влізається в систему ( наприклад число 3 не влізає в двійкову систему, зате повністю вміщається в четвірковій), то воно вважається належним до системи, в яку влізається.

Як вона працює?

  1. Кожне число переводиться з своєї системи в шістнадцяткову, за допомогою функцій

function bintohex(h:string):string;

function quotohex(h:string):string;

function octtohex(h:string):string;

function dectohex(h:string):string;

  1. Виконується операція за допомогою відповідної їй функції

case op of

'+': applyoperation:=longadd(a,b);

'-': applyoperation:=longsub(a,b);

'*': applyoperation:=longmult(a,b);

'/': applyoperation:=longdiv(a,b);

'%': applyoperation:=longmod(a,b);

'^': applyoperation:=longpower(a,b);

end;

Прототип кожної функції майже однаковий і виглядає десь так :

function longadd(a,b:string):string;
Спочатку більшість з них розбирається зі знаками. (якщо додавати від’ємне число до додатного, то це буде віднімання, а не додавання). Потім викликаються функції нижчого рівня, які не мають поняття про від’ємні числа. Наприклад function positivesub(a,b:string):string; для якої завжди a>b , інакше невідомо що буде. Зі всім розбирається функція в назві якої немає слова positive.

Є також функції для перетворення з шістнадцяткової в всі інші системи числення.

Найкрасивіше працює function hextobin(h:string):string; Вона просто замінює кожну шіснадцяткову цифру на послідовність з чотирьох двійкових. Отак:

const binparts:array [0..15] of string[4]=(

'0000','0001','0010','0011','0100','0101','0110','0111','1000','1001','1010','1011','1100','1101','1110','1111');

function dectohex(h:string):string; працює тривіально:

for i:=i to length(h) do

begin

res:=longmulttoint(res,10);

res:=positiveadd(res,h[i]);

end;

І всі інші функції переведення систем працюють також за відомими алгоритмами.
function positivecmp(a,b:string):integer; Порівнює a і b. Якщо а більше то результат 1, якщо менше, то -1, а якщо рівні, то нуль. Вона також не знає, що бувають від’ємні числа.

function chartoint(c:char):integer; показує числове значення символа цифри.

function inttochar(i:integer):char; повертає символ, який позначає цифру. Ці дві функції вміють генерувати помилки.
^ Модуль Tree.

Всі вирази представляються в вигляді дерев. Структура дерева – виразу представляється на малюнку.

type ptree=^ttree;

ttree=record

op:tlexemtype;

val:string;

left:ptree;

right:ptree;

end;



Якщо лексема – змінна, або константа, то вона не має піддерев. (обидва вказівники показники на нуль). Але якщо лексема – операція, то вона виконується над двома, чи одним операндом). Щоб обчислити значення дерева (виразу) потрібно обчислити значення лівого і правого піддерев, а потім, якщо вони константи, то виконати операцію, яка задається лексемою.

Це все робить процедура procedure sprosttree(tr:ptree; syst:integer); яка всі лексеми по замовчуванню вважає в системі syst.

Так як дерева задаються вказівниками, то при присвоєнні одного дерева іншому присвоюються тільки адреси, тобто два вказівники показують на одне дерево. Щоб такого не траплялося зроблена функція function copytree(tr:ptree):ptree;. Яка повертає точну копію дерева tr , але вже в іншому місці памяті. Так як пам'ять не безмежна, то потрібно прибирати непотрібні гілки. Це робить procedure killtree(var tr:ptree); Якщо знищувати дерева просто за допомогою dispose , то ми тільки відрубаємо стовбур, а в памяті залишаться лежати нікому не потрібні ліва і права вітки. Тому killtree спочатку відрубує і знищує гілки, а вже потім решту дерева.

procedure printtree(t:ptree) потрібна для виводу виразів. Вирази виводяться з максимальною кількістю дужок, які показують порядок виконання дерева.
^ Модуль Memory

Запам’ятовує змінні, в списку

type pvariable=^tvariable;

tvariable=record

name:string;

next:pvariable;

value:ptree;

end;

кожен елемент списку (змінна) має ідентифікатор (name) і вираз – значення (value).

Список починається звідси: var list:pvariable; і недоступний за межами модуля.

function getvaraddres(s:string):pvariable; видає адресу за якою знаходиться змінна, якщо відома її назва. Якщо змінної з такою назвою немає, то вона повертає пустий вказівник. Функція function getvalue(name:string):ptree; повертає вже не вказівник, а значення виразу. Вираз буде порожнім, коли змінну не знайшли.

procedure assignval(name:string; val:ptree;syst:integer); пробує спростити вираз в системі syst , а потім присвоює його змінній з назвою name. Якщо такої змінної нема, то вона з’явиться.

procedure deletevar(name:string); стирає змінну. Якщо такої нема, то не стирає.

procedure dumpmemory; виводить список всіх змінних на екран.


^ Модуль lexems
Розпізнає команди

type tcommandtype=(CC_input,CC_output,CS_bin,CS_quo,CS_oct,CS_dec,CS_hex,CC_exit,CC_sleep,CC_help,CC_read,CC_write,CC_cls,CC_dump,CC_none);

CC_none – не команда (щось інше (може вираз))

і лексеми

type tlexemtype=(L_const, - число в якійсь системі числення

L_var, - назва змінної (може складатись з символів множини const alphabet:set of char=['a'..'z','A'..'Z','_','0'..'9'];)
LO_plus, LO_minus, LO_mult, LO_div, LO_mod, LO_power, - арифметичні операції

LO_free, - оператор який звільняє (стирає) змінну з пам’яті. Перед знищенням змінна віддає своє значення оператору. Тобто він навіть має значення. Так як і

LO_assign, - присвоює ідентифікатору зліва значення правого виразу, і як результат повертає правий вираз.

L_eol, - знак того що пора завершувати.

L_leftp, - ліва дужка

L_rightp); - права дужка.
function priority(l:tlexemtype):integer; визначає пріорітет лексеми при побудові дерева.


все що знаходиться в [квадратних дужках] нізащо не буде вважатись ідентифікатором. Тільки числом. Тому, якщо в дужках написати не цифру, з’явиться помилка.
function getcommand(var param:string):tcommandtype; читає команду з буфера, і розпізнає її. При цьому, якщо що то її можна прочитати ще раз, на відміну від function getlexem(var lex:string):tlexemtype; яка читає кожну лексему тільки раз. Вона в різних ситуаціях реагує по різному. Є var prevlexem:tlexemtype; яка зберігає попередню видану лексему. Якщо вона наприклад зустрічає мінус, і перед ним стоїть змінна або константа, то мінус – бінарний. Інакше мінус вважається унарним.

Після діставання лексеми з квадратних дужок викликається whatanumber(lex);

яка викликає помилку, якщо їй передати не число.

Якщо зустрічаємо символ з алфавіту (alphabet:set of char=['a'..'z','A'..'Z','_','0'..'9'];), то ми приклеюємо його до лексеми, і беремо новий, доки не зустрінеться символ не з алфавіту, або кінець рядка.

Далі цю лексему ми шукаємо в списку змінних, і якщо її там нема, то перевіряємо чи вона часом не константа. Якщо вона не константа викликається whatanumber(lex); яка викликає помилку, якщо їй передати не число. Але якщо після лексеми стоїть знак дорівнює, то це значить, що це все таки змінна, яку щоправда ще не створили.


^ Модуль syntax

В модулі знаходиться function gettree:ptree; яка витягає з буферу вводу дерево. Приклад її роботи покроково описано нижче.



















Функція працює за такими правилами.

1.Спочатку дерево пусте.

2. Береться перша лексема.

3. Поки вона не означає кінець рядка

а) Якщо зустрічаємо ліву дужку то витягуємо піддерево (function getsubtree:ptree;), в новий вузол. Його пріорітет 5 ( вираз в дужках)

б) інакше створюємо новий вузол, і записуємо в нього нашу лексему. Піддерева обрізаємо.

в) Якщо це змінна, яка не існує, то створюємо її з пустим виразом, для того, щоб далі впродовж виразу getlex розпізнавало її як змінну.

г) Обчислюємо пріоритет лексеми.

д)Якщо дерево порожнє, то замість стовбура вставляємо нашу гілку. (кадр 2)

є) інакше якщо наш пріоритет менше або рівне пріоритету операції в корені дерева, то лівим піддеревом нашої гілки стає основне дерево. А замість дерева ставимо нашу гілку. (кадр 3)

ж) інакше якщо праве піддерево пусте, то вставляємо туди нашу гілку.

з) інакше шукаємо по правих під деревах два сусідні вузли батька та сина, де батько має менший або рівний пріоритет ніж наша гілка, а син більший. Потім правим сином батька стане наша гілка, а лівим сином гілки стане син батька. (див кадр 5)

4. Беремо наступну лексему і повторюємо все від а) до з).

function getsubtree:ptree; працює аналогічно, але поки не зустріне праву дужку.

procedure executetree(var tr:ptree; syst:integer);

Виконує дерево. На відміну від процедури procedure sprosttree(tr:ptree; syst:integer); яка може виконувати тільки арифметичні операції над константами, вона вміє створювати і видаляти змінні, а також підставляти їх значення в дерево.Якщо дерево пусте, або константа, то більше нічого виконати неможна, і робота завершується. Інакше спочатку рекурсивно викликається для лівого і правого піддерев. Якщо вона зустрічає оператор присвоєння, то підставляє замість нього праве піддерево, і викликає procedure assignval(name:string; val:ptree;syst:integer); яка записує значення змінної в лівому піддереві. Якщо там не змінна, то генерується помилка.

Якщо зустрічає оператор видалення змінної, то підставляє замість нього значення змінної, яка знаходиться в лівому піддереві. Якщо там не змінна, то генерується помилка. Якщо дерево – змінна, то вставляє замість нього значення змінної. Зрозуміло, що всі зайві вузли звільняються.



следующая страница >>