Структури от данни в програмирането 2005/06 - упражнения и практикум

Проект № 1. EXPR - език за прости аритметични изрази и функции

Да разгледаме учебния език EXPR. Той се състои от два типа команди - изрази и дефиниции на функции. Изразите се записват по следния начин:

<израз> ::= <реално-число> | <функция>(<израз>{,<израз>})
<функция> ::= <идентификатор>

Трябва да са заложени стандартните аритметични функции add, sub, mult, div, pow, sqrt, sin, cos.

Другата възможност на езика е да се дефинират собстевни (потребителски) функции. Функциите може да се дефинират по следния начин:

<дефиниция-на-функция> ::= <функция> <- <израз-с-параметри>
<израз-с-параметри> ::= <константа> | #<цяло-число> | <функция>(<израз-с-параметри>{,<израз-с-параметри>})

Тук с #i се означава i-тия аргумент на функцията. За да стане по-ясно действието на езика, да разгледаме следните примери:

Пример 1. Нека е дадена следната програма на EXPR

sub(mult(mult(2,sin(5.7)),cos(5.7)),sin(1.4))

Резултатът от тази програма би трябвало да е 0.

Пример 2.Нека е дадена следната програма на EXPR

sqr <- mult(#0,#0)
sumsqr <- add(sqr(#0),sqr(#1))
x <- 5
sumsqr(mult(1.2,sqr(x())),div(x(),2.0))


Резултатът от тази програма е числото 906.25.

Целта на проекта е да се изпълняват програми на езика EXPR, т.е. да се напише интерпретатор на EXPR.

Насоки

Една идея е да представяте изразите и дефинициите на функции по един и същи начин - дървета, които обаче могат да имат не само 1 или 2 а произволен брой наследници, т.е. да имат списък от наследници. Възлите в тези дървета ще са от няколко типа:

• константа (реално число) - няма наследници
• вградена функция - add, sub, mult, div, pow, sqrt, sin, cos - 1 или два наследника в зависимост от броя на аргументите на функцията
  
• потребителска функция - 0, 1 или повече наследници
• аргумент на функция - няма наследници, съдържа число, което показва номер на аргумента
  

Всички възли могат да са наследници на един и същи базов абстрактен клас, който описва възел и има член-функция evaluate() - тя ще има различна реализация в различните производни класове. Функцията evaluate трябва да приема като параметър масив от стойности на аргументи в случая когато ще пресмятаме потребителски дефинирана функция (за да знае какви числа да сложи на мястото на #-ите).

Намирането на резултата от даден израз (оценката на израза) става по следното правило:

• оценката на константата е самата й стойност
• оценката на вградената функция се получава като се приложи съответната функция над оценките на аргументите й (наследниците на възела)
• оценката на потребителски дефинираната функция е оценката на дървото, описващо дефиницията на функцията, изчислено с evaluate() с параметър стойностите, които се получават като оценки на аргументите й (наследниците на възела)
  
• оценката на аргумент на функция зависи от номера на аргумента и подадения на evaluate() масив

Тогава Вашата задача е да направите програма, която чете команди на EXPR и построява дървета на съответните изрази, като запомня за всяка функция името й и дървото, което описва дефиницията й. За всеки израз, който не е дефиниция на функция, програмата трябва да извежда по едно число - резултатът от изпълнението на функцията.