操車場アルゴリズムのProlog実装

parse.pl

ops(+,1).
ops(*,2).
parse(O,S,[],R):-!,parse3(O,S,R).
parse(O,S,['('|C],R):-!,parse(O,['('|S],C,R).
parse(O,S,[')'|C],R):-!,parse1(O,S,C,R).
parse(O,S,[A|C],R):-atom_number(A,I),!,parse([I|O],S,C,R).
parse(O,S,[V|C],R):-ops(V,P),!,parse2(P,O,S,[V|C],R).
parse(_,_,_,_):-throw('InvalidToken').
parse1(_,[],_,_):-throw('ParenthesisMismatch').
parse1(O,['('|S],C,R):-parse(O,S,C,R).
parse1(O,[V|S],C,R):-parse1([V|O],S,C,R).
parse2(P,O,[V|S],C,R):-ops(V,P1),P>=P1,parse2(P,[V|O],S,C,R).
parse2(_,O,S,[V|C],R):-parse(O,[V|S],C,R).
parse3(O,[],O):-!.
parse3(_,['('|_],_):- throw('ParenthesisMismatch').
parse3(O,[V|S],R):- parse3([V|O],S,R).
vm(S,[],S).
vm(S,[I|C],R) :- integer(I),vm([I|S],C,R).
vm([A,B|S],[O|C],R) :-vm([[O,B,A]|S],C,R).
parse(A,R):-atom_chars(A,C),parse([],[],C,R).
:- parse('1+2*(3*(4+5)+6)',C),!,reverse(C,C2),vm([],C2,R),writeln(R).
:- halt.