8.1.Двоично дърво.Представяне.Основни операции
   8.2.Граф.Представяне.Основни операции
   8.3.Пролог и КС-граматики
   8.4.Пресмятане на стойност на аритметичен израз
   8.5.Интерпретатор на подмножество на езика Пролог

    
 8.4. Пресмятане на стойност на аритметичен израз
  
  Ще илюстрираме два подхода за пресмятане на стойност на аритметичен израз:

  Първи подход: Аритметичният израз се преобразува в обратен полски запис, след което се пресмята.
  Втори подход: Конструира се КС-граматика, която прави граматичен разбор на алгебричния израз.

    
 Преобразуване на аритметичен израз от обикновен(A) в обратен полски запис(C)   

  Ще разгледаме аритметични изрази без скоби и съдържащи аритметичните операции +, -, *,/.
  За целта ще използваме стек S.
  
  Правилата за движение са следните:
   а) Величините (константи или променливи) се преместват директно 
   б) Операциите +, -, *,/ се включват, като всяка операция има определен приоритет. За обработката
  им въвеждаме тегло на всяка от тях. Приемаме, че + и - са по-тежки от * и /. 
  Ако при включване на операция в стека, под нея има по-лека или равна по тегло операция, по-леката
  или равната по тегло операция се премества от в областта С. Това се повтаря докато под тази, която
  обработваме има по-тежка или стекът стане празен.
   в) Ако всички символи от областта А са обработени, елементите на стека, до изпразването му, се
  прехвърлят в областта С. 

  Задача 1: Да се напише програма, която преобразува аритметиче израз без скоби от обикновен в 
            обратен полски запис.
  Решение: Отношението transf(A, C, S), реализира описания по-горе подход. За представането на
           разклоненията А, С, S ще използваме списъци.
  Имаме:
        transf([], [], []) :- !.
        transf([Op|A), C, []) :- operator(Op), !,
                                 transf(A, C, [Op]).
        transf([Op1|A], [Op2|C], [Op2|S) :- operator(Op1),
                                            weight(Op1, T1),
                                            weight(Op2, T2),
                                            T2 =< T1, !,
                                            transf([Op1|A], C, S).
        transf([Op1|A], C, [Op2|S]) :- operator(Op1), !,
                                       weight(Op1, T1),
                                       weight(Op2, T2),
                                       transf(A, C, [Op1, Op2|S]).
        transf([P|A], [P|C], S) :- transf(A, C, S).
        transf([], X, X).

        operator(*).
        operator(/).
        operator(+).
        operator(-).
        
        weight(*, 1).
        weight(/, 1).
        weight(+, 2).
        weight(-, 2).

  Пример:
         ?- transf([a, *, b, +, c, /, d], X, []).
          X = [a, b, *, c, d, /, +]
          yes

 Пресмятане на стойността на аритметичен израз, записан в обратен полски запис
  Ще реализираме следния подход: Сканира се изразът, записан в обратен полски запис, отляво надясно
  до намиране на операция. Пресмята се стойността на терма с аргументи първите два, намиращи се
  непосредствено пред операцията. Операциите и операндите се заменят с резултата от пресмятането.
  Процесът на търсене на операция и пресмятане продължава до края на израза.
  За целта е удобно да се използва стек. Ще го представим чрез списък.

  Задача 2: Даден е непразен списък, съдържащ правилен обратен полски запис на аритметичен израз,
            съдържащ цели числа и знаци за аритметични операции. Да се пресметне стойността на израза.
  Решение:
        value([Op|E], [X, Y|S], V) :- operator(Op), !,
                                       (Op = +, M is Y + X;
                                        Op = -, M is Y - X;
                                        Op = *, M is Y * X;
                                        Op = /, M is Y / X),
                                       value(E, [M|S], V).
        value([A|E], S, V) :- value(E, [A|S], V).
        value([], [V], V).

        operator(*).
        operator(/).
        operator(+).
        operator(-).

     Пример:
     ?- value([3, 5, 4, +, *], [], N).
      N = 27
      yes