# 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.

- Pages
- Home
- Kattis Info
- Projects
- External Links
- Python Docs
- Kattis Site