1

私はこれを自分で解決しました。宿題の期日を過ぎたときに解決策を投稿します。

さて、私はパーサーまたはエバリュエーターを構築するつもりです。プレフィックス表記で解析するときの事実上の標準は、スタックを使用することです。入力が数値の場合はスタックに追加します。演算子の場合は、演算子を 2 回ポップして結果をスタックに戻すことができます。

ここでのスタックはリストになるため、演算子を適用する方法を知る必要があります。入力は文字列になります。"(11+2*)" これは 1+1=2*2=4 になります。最初に 1 を読み取り、スタックに 1 を読み取ります。別の 1 を読み取り、それをスタックに追加します。今度は "+" と表示されるので、スタックから 2 回削除 (ポップ) し、+ を適用して結果を戻します。2 を読み取り、スタックに 2 を置きます。*を読んで、2回ポップして適用*。

これが理にかなっていることを願っています。述語はどのようになりますか？入力文字列用に 1 つの変数、スタックを維持するために 1 つ、結果用に 1 つの変数が必要ですか? 三？

スタックでのプッシュとポップ、および入力文字列からの削除について特に疑問に思っています。

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 に答える