In this exercise, you will write a Python version of the infix-to-postfix conversion algorithm. In the next exercise, you will write a Python version of the postfix expression evaluation algorithm. Write a program that converts an ordinary infix arithmetic expression (assume a valid expres- sion is entered) with single-digit integers such as (6 + 2) * 5 - 8 / 4 to a postfix expression. The

Question

postfix version of the preceding infix expression is 6 2 + 5 * 8 4 / -

The program should read the expression into a sequence infix, and use modified versions of the stack functions implemented in this chapter to help create the postfix expression in sequence postfix. The algorithm for creating a postfix expression is as follows:
1) Push a left parenthesis '(' onto the stack.
2) Append a right parenthesis ')' to the end of infix.
3) While the stack is not empty, read infix from left to right and do the following:
If the current character in infix is a digit, copy it to the next element of postfix.
If the current character in infix is a left parenthesis, push it onto the stack.
If the current character in infix is an operator,
Pop operators (if there are any) at the top of the stack while they have equal or
higher precedence than the current operator, and insert the popped
operators in postfix. Push the current character in infix onto the stack.
If the current character in infix is a right parenthesis
Pop operators from the top of the stack and insert them in postfix until a left
parenthesis is at the top of the stack.
Pop (and discard) the left parenthesis from 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) Function convertToPostfix that converts the infix expression to postfix notation.
b) Function isOperator that determines if c is an operator.
c) Function precedence that determines if the precedence of operator1 is less than, equal to or greater than the precedence of operator2. The function returns -1, 0 and 1, respectively.
d) Function push that pushes a value onto the stack.
e) Function pop that pops a value off the stack.
f) Function stackTop that returns the top value of the stack without popping the stack.
g) Function isEmpty that determines if the stack is empty.
h) Function printStack that prints the stack.

Answer 1

```
# Class Stack definition with method stackTop.

from ListModule import List

class Stack ( List ):
"""Stack composed from linked list"""

def __init__( self ):
"""Stack constructor"""

self._stackList = List()

def __str__( self ):
"""Stack string representation"""

return str( self._stackList )

def push( self, element ):
"""Push data onto stack"""

self._stackList.insertAtFront( element )

def pop( self ):
"""Pop data from stack"""

return self._stackList.removeFromFront()

def isEmpty( self ):
"""Return 1 if Stack is empty"""

return self._stackList.isEmpty()

def stackTop( self ):
"""Return top value without removing element"""

if self.isEmpty():
return None

return self._stackList._firstNode._data
```
```
# Implement the infix-to-postfix conversion algorithm.

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

def convertToPostfix( infix ):

myStack = Stack()

postfix = ""

# push left parenthesis onto stack
myStack.push( ’(’ )

# append a right parenthesis to end of infix
infix += ’)’

current = 0

while not myStack.isEmpty():

character = infix[ current ]

# append digit to postfix
if character.isdigit():
postfix += character

# push left parenthesis onto stack
if character == "(":
myStack.push( character )

if isOperator( character ):

# if operators on stack have equal or higher precedence
# than the current operator
while isOperator( myStack.stackTop() ):

if precedence( myStack.stackTop(), character ) >= 0:
postfix += str( myStack.pop() )
else:
break # lower precedence

myStack.push( character )

if character == ")":

while myStack.stackTop() != "(":
postfix += str( myStack.pop() )

myStack.pop() # pop and discard left parenthesis

current += 1

return postfix

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

print convertToPostfix( expression )
```
Please enter a mathematical expression: (6 + 2) * 5 - 8/4
62+5*84/-