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
Show Me The Code
Before we get started, the finished Reverse Polish Notation Calculator implementation can be found here. 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
Well, last week I implemented a stack in Google Sheets, and it looks like that's all this program really needs!
The finished Sheet
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:
Calculating the length of a new array.
If we add an element, +1, if we perform an operation, -1
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 IFs. 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.
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
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.
This wonderful post has received a @maxg 15.38% upvote from @mrswhale. Discord Channel: https://discord.gg/XG4y3mg Be sure to vote for witnesses at https://steemit.com/~witnesses
This post has received a 0.57 % upvote from @buildawhale thanks to: @maxg. Send at least 1 SBD to @buildawhale with a post link in the memo field for a portion of the next vote.
To support our daily curation initiative, please vote on my owner, @themarkymark, as a Steem Witness