Prolog parse postfix math expressions

Question

I solved this my self. I'll post the solution when were past due date for my homework.

Okay, I'm going to build a parser or an evaluator. The de facto standard when parsing with prefix notation is to just use a stack. Add to the stack if input is a number, if it is an operator you can pop twice apply operator and put the result back on the stack.

The stack here would be a list, so I need to know how I can apply the operators. The input would be a string. "(11+2*)" This would 1+1=2*2=4. First it would read 1, and 1 to the stack. Read another 1 and add it to the stack. Now it reads "+", so it removes(pop) twice from the stack and apply + and puts the result back. Read 2, put 2 on the stack. Read *, pop twice and apply *.

Hope this makes sense. How would the predicate look like? I need one variable for the input string, one to maintain the stack, and one for the result? Three?

I'm especially wondering about push and pop on the stack as well as removing as I go from the input string.

Answer 1

I'll post the teacher's solution:

% 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,[]).

I'm posting the whole file as it is. The following shows how it works:

?- 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