Пролог разбирать постфиксные математические выражения

Question

Я решил это сам. Я опубликую решение, когда наступит срок моей домашней работы.

Хорошо, я собираюсь собрать анализатор или анализатор. Стандарт де-факто при разборе с префиксной нотацией - просто использовать стек. Добавьте в стек, если input - это число, если это оператор, вы можете дважды применить оператор apply и вернуть результат обратно в стек.

Стек здесь будет список, поэтому мне нужно знать, как я могу применить операторы. На входе будет строка. «(11 + 2 *)» Это будет 1 + 1 = 2 * 2 = 4. Сначала он будет читать 1 и 1 в стек. Прочитайте еще 1 и добавьте его в стек. Теперь он читает «+», поэтому он удаляет (pop) дважды из стека и применяет + и возвращает результат обратно. Прочитайте 2, положите 2 в стек. Прочитайте *, поп дважды и примените *.

Надеюсь, это имеет смысл. Как будет выглядеть предикат? Мне нужна одна переменная для входной строки, одна для поддержки стека и одна для результата? Три?

Мне особенно интересно, что такое push и pop в стеке, а также удаление, когда я иду из строки ввода.

Answer 1

Я выложу решение учителя:

% Løsning oblig 3, INF121, Høsten 2009.
% Skrevet av: Dag Hovland
% Opphavsrett: Universitetet i Bergen
% Lisensiert under GPL v3, www.gnu.org. Etter tillatelse fra administrasjonen.


% Oppgave 1

alignment([],[],[]).
alignment([X|Xs],[X|Ys],[X|A]) :- alignment(Xs,Ys,A).
alignment(Xs,[_|Ys],A) :- alignment(Xs,Ys,A).
alignment([_|Xs],Ys,A) :- alignment(Xs,Ys,A).


maximum([X|Xs],Max) :- maximum(Xs,X,Max).

maximum([],(X,_),X).
maximum([X|Xs],(_,LM),MX) :- length(X,LX), LX > LM, !, maximum(Xs, (X,LX), MX).
maximum([X|Xs],(M,LM),MX) :- length(X,LX), LX < LM, !, maximum(Xs, (M,LM), MX).
% Pga. kuttene over vet vi at dersom tilfellene under brukes, så er
% X akkurat like lang som lengste sett så langt 
maximum([X|Xs],_,MX) :- length(X,LX), maximum(Xs, (X,LX), MX).
maximum([_|Xs],M,MX) :- maximum(Xs, M, MX).

maxAlignment(Xs,Ys,A) :- findall((N,A),alignment(Xs,Ys,N,A),All),!,
    maximum(All,(_,A)).

% Oppgave 2

path(S,S,_).
path(S,End,Edges) :- select((S,Next),Edges,EdgesRest),
    path(Next, End, EdgesRest).

% select er innebygd. Skriv "listing(select) for å se definisjonen:
%select(A, [A|B], B).
%select(B, [A|C], [A|D]) :-
%   select(B, C, D).

% polish(I,V,S) evaluates expression I to value V with stack S.
polish([],V,[V]).
polish(I,V,S) :- append(" ",I1,I),polish(I1,V,S).
polish([NC|I],V,S) :- name(N,[NC]),integer(N),polish(I,V,[N|S]).
polish(I,V,[F1,F2|S]) :- append("+",I1,I),Sum is F1+F2,polish(I1,V,[Sum|S]).
polish(I,V,[F1,F2|S]) :- append("-",I1,I),Sum is F2-F1,polish(I1,V,[Sum|S]).
polish(I,V,[F1,F2|S]) :- append("/",I1,I),Sum is F2/F1,polish(I1,V,[Sum|S]).
polish(I,V,[F1,F2|S]) :- append("*",I1,I),Sum is F1*F2,polish(I1,V,[Sum|S]).

evalPost(S,E) :- polish(S,E,[]).

Я выкладываю весь файл как есть. Ниже показано, как это работает:

?- evalPost("1 2 3 * +", V).
V = 7
?- evalPost("1 3 2 * 2 + +",V).
V = 9
?- evalPost("1 2 3 * 4 + +",V).
V = 11
?- evalPost("1 2 3 * 4 + -",V).
V = -9
?- evalPost("4 2 / 1 +",V).
V = 3