Postfix expression list evaluation

Question

I have written a program to evaluate a post-fix expression in prolog recursively from an expression list. For example, given the following list:

[+,1,2]

It should return 3. They way I have constructed my predicate is to call itself recursively until it reaches the end of the list so that it reads values backwards. (the same as reading this list from left to right:[2,1,+]).

My problem is that when I try to return more than one value through the recursive calls all the values suddenly disappear.

Here's the code:

eval_list([Head|Tail],_,Result):-
   Tail==[], % last element of list
   Result=Head,
   write(Head),
   write(' was stored in Result!\n').

eval_list([Head|Tail],Store1,Result):-
      eval_list(Tail,Store2, NewResult),
      (\+integer(Store2))
   ->
      % if no integer is bound to Store2, bind Store1 to Head
      Store1=Head,
      Result is NewResult,
      write(Head),
      write(' is stored value!\n')
   ;  (integer(Store2)) ->
    % if an integer is bound to store2, we perform operation specified by the Head with the stored number
      X is Store2+NewResult,
      Result is X,
      write('performed operation!\n')
   ;
      % if doesnt catch either of these states the program is broken
      (  print('something broke\n'),
         print(Store1),
         nl,
         print(Store2),
         nl,
         print(Head),
         nl,
         print(Result),
         nl
      ).

I get the following output:

?- eval_list([+,1,2],X,Result).
2 was stored in Result!
1 is stored value!
something broke
_G1162
_L147
+
_G1163
true.

I don't understand why my values disappear, or if there is a better way to evaluate the list.

Unknown Unknown · Accepted Answer · 2013-04-11T11:38:06

Some advice on your programming technique. You should use head matching and unification instead of explicit unification in the body of your predicate definitions, and if-else constructs. You should also avoid not tail-recursive recursion, unless your algorithm is inherently recursive (in-order tree traversal, for example). This will make the code easier to write, read, and understand. Right now, I don't even feel like debugging your code, but it looks like your Store2 would never be bound to an integer, and is always going to be an unbound variable, no matter what input your program has.

Now to your program. It is not clear what you are trying to achieve. If you only want to evaluate list of the form [Arithmetic_operator, Operand1, Operand2], it would be much easier to write:

arith_eval(Expression_list, Result) :-
    Arithmetic_expr =.. Expression_list, % look up what =.. stands for!
    Result is Arithmetic_expr.

I don't see the need for this overly complicated approach you are using.

If you want to be able to evaluate arbitrarily complex expressions, written in post-fix, with fixed operator arity (so you can say 2, 3, +, but not 2, 4, 1, +, for a sum of 7):

Read one element from your input
- Push the element to the top of the stack
- Try to reduce the stack:
  - pop operator and operands, if on top of the stack
  - evaluate
  - push result back on the top of the stack
When input is empty, your stack is your result

You could explicitly define the effect of different operators (here, only + and -) like this:

eval_stack([+,A,B|Tail],[Result|Tail]) :-
    number(A), number(B),
    !,
    Result is B + A.
eval_stack([-,A,B|Tail],[Result|Tail]) :-
    number(A), number(B),
    !,
    Result is B - A.
eval_stack(Stack,Stack).

Note how either an operator matches the top of your stack, and is applied when there are operands below it, pushing the result back on the stack, or the stack is left unchanged.

And you can push from your input to your stack:

evaluate([Next|Rest], Stack, Result) :-
    eval_stack([Next|Stack],NewStack),
    evaluate(Rest,NewStack,Result).
evaluate([],Result,Result). % end of input

So now you could call this with:

?- evaluate([2,3,+,3,6,-,+],[],Result).
Result = [2].

?- evaluate([2,3,4,-,-,5,+],[],Result).
Result = [8].

?- evaluate([2,3,4,-,-,5,+,1,3,2,-],[],Result).
Result = [1,1,8].

So these two predicates, evaluate(Input,Stack,Result), and eval_stack(Stack,NewStack) is all you would need for evaluating a valid post-fix arithmetic expressions with fixed-arity operators only.

Postfix expression list evaluation

1 Answers