1

我自己解决了这个问题。当我的作业过期时,我会发布解决方案。

好的,我将构建一个解析器或评估器。使用前缀表示法解析时的事实标准是仅使用堆栈。如果输入是数字,则添加到堆栈中,如果是运算符,则可以弹出两次应用运算符并将结果放回堆栈。

这里的堆栈将是一个列表,所以我需要知道如何应用运算符。输入将是一个字符串。“(11+2*)” 这将是 1+1=2*2=4。首先它将读取 1 和 1 到堆栈。读取另一个 1 并将其添加到堆栈中。现在它读取“+”,因此它从堆栈中删除(pop)两次并应用+并将结果放回。读取 2,将 2 放入堆栈。阅读*,弹出两次并应用*。

希望这是有道理的。谓词会是什么样子?我需要一个用于输入字符串的变量,一个用于维护堆栈,一个用于结果?三?

我特别想知道堆栈上的推送和弹出以及从输入字符串中删除。

4

1 回答 1

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
于 2010-07-04T21:06:03.633 回答