Algorithm to evaluate a prefix expression

Algorithm

Suppose P is an expression written in prefix notation. This algorithm finds VALUE of prefix expression P.

1) Add ‘(’ in the beginning of P.
2) Scan P from right to left and repeat step3 and step4 for each symbol of P until sentinel ‘(’ is encountered.
3) If an operand is encountered, push it onto stack
4) If an operator  is encountered, then
a) Pop two elements from the stack, where A is topmost element and B is next to top element.
b) Evaluate AB.
c) Push above result onto stack.
5) VALUE ← top element on the stack.
6) Exit.