Stack Calculator

A stack is a data structure in which has two operations:

  • A push operation which adds an item to the top of the stack
  • A pop operation which removes the top item from the stack

In other terms, it is a “last in, first out” data structure. Think of it like a stack of pancakes, the most recently baked pancake will be eaten first.

In Python, we can treat a simple list as a stack. Say we have a list called numstack, then we can use the following operations:

  • numstack.append(item) to push item to the stack
  • numstack.pop() to remove and get the value of the top item from the stack (pop)

Additionally, we can peek at the stack. This would be to look at the top without removing from it. Looking at index -1 of a list would get the last item in a sequence, so we can peek by doing numstack[-1].

RPN Calculators

Reverse Polish Notation (RPN) calculators take advantage of a stack to perform arithmetic expressions without requiring the user to enter parenthesis. For example, the operation 3 + 4 would be written 3 4 + on a RPN calculator.

How does this work? First, when the user enters 3, the number 3 is pushed to the stack. Then, when they type in 4, 4 is pushed to the stack. Finally, when they type in +, the top two items are popped from the stack, added together, then the result was pushed to the stack for further operations.

This allows us to do more complex operations. If you wanted to calculate (3 + 4) * 2, you could enter this as 3 4 + 2 *, no parenthesis needed!

Implementing your Calculator

Your goal is to implement an interative calculator with quite a few operators. In my RPN calculator I made in Python, I implemented operators using words, like add and mul. This is a style choice that will ultimately be up to you in your project.

Here is an example with my calculator:

> 3 4 add pop
7
>

In this example, first 3 and 4 would be pushed to the stack, the add operator calculated 3 + 4, then pushed 7 to the stack, and finally, the pop operator popped the top item from the stack and printed it. The calculator then continued to prompt for input.

This line could have just as easily been split up into multiple, as my program keeps track of the stack between lines.

> 3
> 4
> add
> pop
7
>

Some Advice

Keep track of a global stack, then process each number or operator, modifying your global stack that way. Depending on how simple your syntax is, calling .split() on your input should be sufficent to tokenize it.

There are a few ways you could implement operators. One way might be to simply keep a long if/elif of your operators as you process them. Here is an example:

if op == 'add':
    stack.append(stack.pop() + stack.pop())
elif ...

However, as you can imagine, this will get nasty, very fast! One potential alternative is to implement each of your operators in a function, then use a dictionary mapping of operator name to function:

stack = []
def _operator_add():
    stack.append(stack.pop() + stack.pop())
...

op_table = {
    "add": _operator_add,
    ...
}

while True:
    line = input("> ").split()
    for word in line:
        if word in op_table.keys():
            op_table[word]()
        else:
            stack.append(int(word))

The last option is to take advantage of a very special dictionary in Python. Because calling globals() will return a dictionary of all defined global variables — including functions, we can avoid making the op_table above.

def _operator_add():
    stack.append(stack.pop() + stack.pop())
...

while True:
    line = input("> ").split()
    for word in line:
        if "_operator_" + word in globals().keys():
            globals()["_operator_" + word]()
        else:
            stack.append(int(word))

Thinking very carefully about how you will structure your program before you start will go a long way.