Topic of NAP class on Aug. 14, 2017
RPN is also called postfix notation. To sum, it is a mathematical notation in which operators follow their operands (e.g. “3+6” is equivalent to “36+”) and it generally does not include parenthesis.
Our task is to create an RPN Calculator function in Python assuming all numbers are single digits, the input will already be in RPN, and a First In Last Out stack is used (e.g.: Stacking plates in a restaurant is a FILO stack as you should not try to take out the bottom plate unless it is last.). Bonus if you can make a function to convert infix notation (including parenthesis) to RPN (expect to be assigned this next time).
The following seven methods/functions will be needed:
- push
- pop
- oper +
- oper -
- oper *
- oper /
- main
If the pop and push methods on lists do not operate as a FILO stack, then you will have to make your own.
Hint
The pop and push methods do act as a FILO stack.
The example given in class was to calculate the following equation with the RPN calculator:
First, we can expand it to:
((a*a) + ((b+c) * (b+c)))/(3*a)
And then convert it to RPN as:
aa*bc+bc+*+3a*/
Now, the above RPN equation can be input into our function to give a result. Such as:
print(rpn("aa*bc+bc+*+3a*/"))
If we had to make our own push and pop functions, they would look something like:
def pop(s):
val = s[0:]
s = s[1:]
return val
def push(s,val):
return s = s + val
The main function, rpn, would look something like:
def rpn(str):
for s in str:
if s = '+-*/':
oper1 = pop
oper2 = pop
if s = '+':
push oper1 + oper2
elif s = '-':
push oper2 - oper1
elif s = '*':
push oper1 * oper2
else:
push oper2 / oper1
push s
return pop
Note
- The rpn function consists of pseudocode and will not work if used as-is.
- The order of operands matters for both ‘/’ and ‘-‘ as they are noncommutative operations.
- If the element in the string is not an operator, it can safely be pushed onto the stack.
- The operator functions were implemented in the rpn function as if-else statements.
Can you tell I was a Teaching Assistant?
Solution can be found as a gist on github WARNING! Contains Spoilers!
I plan on making it a bit more robust because it can break easily as-is.