Prolog解析後綴數學表達式

Question

我解決了這個我的自我。當我的作業過期時，我會發布解決方案。

好吧，我要建立一個解析器或一個評估器。使用前綴符號解析時的事實標準是僅使用堆棧。如果輸入是數字，則添加到堆棧;如果它是一個操作符，則可以兩次彈出應用操作符並將結果放回堆棧。

這裏的堆棧將是一個列表，所以我需要知道如何應用操作符。輸入將是一個字符串。 「（11 + 2 *）」這將1 + 1 = 2 * 2 = 4。首先它會將1和1讀入堆棧。讀另一個1並將其添加到堆棧。現在它讀取「+」，因此它從堆棧中刪除（彈出）兩次並應用+並將結果返回。閱讀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