Examples Postfix Infix Result 2121 545-4 7 2*7 * 2 93/9/3 25 7 "(2+5) * 7 49 3
Part 1: Stack
As mentioned in class, Python 3 provides the LifoQueue class as part of the Queue library. To see how this is really just a wrapper around the basic list class below is our own Stack class that uses a list.
Copy this code into file lab5.py
You MAY NOT change the below code anyway.
class Stack:
def __init__(self):
self.__S = []
def __str__(self):
return str(self.__S)
def push(self,x):
self.__S.append(x)
def pop(self):
return self.__S.pop()
def top(self):
return self.__S[-1]
Part 2: Postfix Math
You are probably most familiar with math written in infix notation. For example, "4 + 3 - 7". In infix notation, operators are placed between their inputs. This is a very nice way to read math, but it is nontrivial for a computer to parse.
An alternative representation is called postfix notation. In postfix, we write the two inputs followed by the operator. The previous example would be "4 3 + 7 -". This is much easier to parse because we have both inputs before the operator. We also don't have to worry about parenthesis.
Postfix notation works well with a Stack.
- Push Numbers onto Stack as read from input.
- When operator seen:
- Pop top 2 items on stack.
- Complete Operation.
- Push result onto Stack.
- Repeat until end of input.
- Final Result will be on top of Stack.
Implement a function postfix(exp) that takes a string exp containing a postfix math expression as input and returns the result as a float.
You MUST use the provided Stack class to implement this function.
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 1 images
