Prolog parse postfix expressions mathématiques

Question

J'ai résolu ce moi-même. Je posterai la solution à la date d'échéance de mes devoirs. OK, je vais construire un analyseur ou un évaluateur. La norme de facto lors de l'analyse avec la notation de préfixe est d'utiliser simplement une pile. Ajouter à la pile si l'entrée est un nombre, si c'est un opérateur, vous pouvez sauter deux fois appliquer l'opérateur et mettre le résultat sur la pile.

La pile ici serait une liste, donc j'ai besoin de savoir comment je peux appliquer les opérateurs. L'entrée serait une chaîne. "(11 + 2 *)" Ce serait 1 + 1 = 2 * 2 = 4. D'abord, il lirait 1, et 1 à la pile. Lisez-en un autre et ajoutez-le à la pile. Maintenant, il lit "+", donc il supprime (pop) deux fois de la pile et applique + et renvoie le résultat. Lisez 2, mettez 2 sur la pile. Lisez *, sautez deux fois et appliquez *.

Espérons que cela a du sens. À quoi ressemblerait le prédicat? J'ai besoin d'une variable pour la chaîne d'entrée, un pour maintenir la pile, et un pour le résultat? Trois?

Je m'interroge tout particulièrement sur les fonctions push et pop sur la pile ainsi que sur la suppression de la chaîne d'entrée.

Answer 1

Je posterai la solution de l'enseignant:

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

Je posterai tout le fichier tel qu'il est. L'exemple suivant montre comment ça marche:

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