# Learn Data Structures the Insane Way - Reverse Polish Notation Calculator in Google Sheets

People joke all the time about how tools like Google Sheets and Excel are usable for functional programming. Unfortunately, I've never seen more than a toy example. I'd like to change that. I'm going to release a series of functional programming posts using only Google Sheets. If you'd like to follow along, hit the follow button and check in every few days!

This is the second post in a series. The first one can be found [here](https://steemit.com/programming/@maxg/learn-data-structures-the-insane-way-implementing-a-stack-in-google-sheets)

## Show Me The Code

Before we get started, the finished Reverse Polish Notation Calculator implementation can be found [here](https://docs.google.com/spreadsheets/d/16g1iz1B9QvnRfKb-KVtJMLVUerg_21SprrDol7WhKNI/edit?usp=sharing). Feel free to create your own copy, mess around, etc.

What is Reverse Polish Notation?

Reverse Polish Notation is a way of writing algebraic equations so that you don't need parenthesis to determine order of operations. This is done by placing the operator after the operand. Instead of `1 + 1` you would write `1 1 +`. Then, read left to right and whenever you find an operand (`+ - / *`), evaluate it with the two numbers to the left. After evaluating a partial expression, the result replaces the partial expression. An example:
```
3 4 - 5 +  
(3 4 -) 5 +
-1 5 + 
4
```

The pseudocode for evaluating any Reverse Polish Notation expression is as follows: 
```
for each token in the postfix expression:
  if token is an operator:
    operand_2 ← pop from the stack
    operand_1 ← pop from the stack
    result ← evaluate token with operand_1 and operand_2
    push result back onto the stack
  else if token is an operand:
    push token onto the stack
result ← pop from the stack
```
Taken from Wikipedia [src](https://en.wikipedia.org/wiki/Reverse_Polish_notation#Postfix_evaluation_algorithm)

Well, last week I implemented a stack in Google Sheets, and it looks like that's all this program really needs!

## The finished Sheet
![](https://steemitimages.com/DQmV3U68YPG16FhjeGJWNBhf8YKPDycsrMUrErXwkdjvGGe/image.png)

## The main idea

Each column represents one cycle of the for loop, and we require one column for every character in the postfix expression. We decide if we are adding a new element to the new array or cutting two elements off and adding the result of performing the operation. At the end we will have an array of length one where the only element is our answer. 

## Code Snippets:
![](https://steemitimages.com/DQmShAB7gBAqTCGCwTZuR6rmNncgivXtcEtE9fPTQFWecRY/image.png)
#### Calculating the length of a new array. 
If we add an element, +1, if we perform an operation, -1


![](https://steemitimages.com/DQmcRgDJ3tg9LACpW8vnwV6oX2cfHjv4HSVAPvrDt9T1sdu/image.png)
#### Calculating the New Element
```
=IF(D8,
    IF(EXACT(D7,"-"),
       D11-D10,
       IF(EXACT(D7,"+"),
          D10+D11,
          IF(EXACT(D7,"/"),
             D11/D10,
             D10*D11)
          )
       ),
    D7)
```
Unfortunately, Google Sheets doesn't have case statements, so we end up with this chain of `IF`s. All it does is string compare the input to the string literals `"+" "-" "*" "/"` and perform the appropriate calculation, or return the input number if not an operand.


![](https://steemitimages.com/DQmfH8DqH9b7AePu1rHrkryxkN1n3zoLTepSaesPvhrkA51/image.png)
#### Calculating the new array
We cut the old array down to the appropriate length and concat it with the value generated above. Pretty straightforward stuff, but it still feels cool watching it all come together in a spreadsheet tool.

## Thanks for reading!
If you've got any ideas for posts in the future, let me know in the comments!
Play around with the calculator yourself [here](https://docs.google.com/spreadsheets/d/16g1iz1B9QvnRfKb-KVtJMLVUerg_21SprrDol7WhKNI/edit?usp=sharing)
If you have a better idea for how to share Google Sheets code, let me know. I'm not a fan of the screenshot approach.