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 pushitem
to the stacknumstack.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.