Write a postfix evaluator, which evaluates a postfix expression (assume it is valid) such as 6 2 + 5 * 8 4 / -

Question

The program should read a postfix expression, such as the one created in Exercise 22.4. Using modified versions of the stack methods implemented in this chapter, the program should scan the expression and evaluate it. The algorithm is as follows:
1) Read the expression from right to left.
If the current character is a digit:
Push it on the stack.
Otherwise, if the current character is an operator:
Pop the two top elements of the stack into variables x and y.
Calculate y operator x.
Push the result of the calculation onto the stack.
2) At the end of the postfix expression, pop the top value of the stack. This is the result of
the postfix expression.
[Note: In 1) above (based on the sample expression at the beginning of this exercise), if the operator
is ’/’, the top of the stack is 2 and the next element in the stack is 8, then pop 2 into x, pop 8 into y,
evaluate 8 / 2 and push the result, 4, back on the stack.]
The following arithmetic operations are allowed in an expression:
+ addition
- subtraction
* multiplication
/ division
** exponentiation
% modulus
The stack should be maintained with stack nodes that each contain a data member and a reference to the next stack node. Some of the functional capabilities you may want to provide are:
a) Method evaluatePostfixExpression, which evaluates the postfix expression.
b) Method calculate, which evaluates the expression op1 operator op2. [Note:
Method eval returns the result of an expression. For example, eval( ’2**4’) returns
16.]
c) Method push, which pushes a value on the stack.
d) Method pop, which pops a value off the stack.
e) Method isEmpty, which determines if the stack is empty.
f) Method printStack, which prints the stack.

Answer 1

```
# Evaluate a postfix expression.

from StackModule import Stack

# Return 1 if c is an operator, 0 otherwise
def isOperator( c ):
return c in [ ’+’, ’-’, ’**’, ’/’, ’%’, ’*’ ]

# Determine precedence of operator1 compared to operator2
def precedence( operator1, operator2 ):

# precedence lists
highest = [ ’**’ ]
middle = [ ’/’, ’%’, ’*’ ]
lowest = [ ’+’, ’-’ ]

# trivial case - operators are the same
if operator1 == operator2:
return 0

# exponential operator has highest precedence
if operator1 in highest and operator2 not in highest:
return 1

if operator1 in lowest and operator2 not in lowest:
return -1

if operator1 in middle:

if operator2 in highest:
return -1

elif operator2 in lowest:
return 1

# operators have the same precedence
return 0

# use eval to return the result of an expression
def calculate( expression ):
return eval( expression )

# return the result of a postfix expression
def evaluatePostfixExpression( postfix ):

myStack = Stack()

# read postfix expression right to left
for character in postfix:

# if character is a digit, push it on the stack
if character.isdigit():
myStack.push( character )

if isOperator( character ):

# pop the top two elements
y = myStack.pop()
x = myStack.pop()

# push result on stack
myStack.push( calculate( str( x ) + character + str( y ) ) )

# return the top value of the stack - the result
return myStack.pop()

expression = raw_input( "Please enter a postfix expression: " )

print evaluatePostfixExpression( expression )
```
Please enter a postfix expression: 6 2 + 5 * 8 4 / -
38