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:

  1. push
  2. pop
  3. oper +
  4. oper -
  5. oper *
  6. oper /
  7. 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:

Image of the equation a squared plus b plus c squared divided by 3 times a

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.