In my journey of creating a programming language, I faced an issue: how to handle mathematical expressions with operator precedence properly without having to write a big ass algorithm? So after long long researches, I found the Reverse Polish Notation, a mathematical notation made exactly for that and used in all modern calculators!
Reverse Polish Notation (or RPN) is a Postfix notation (operators after operands) while our mosly used notation is an Infix notation (operators between a left and right operands).
But how to easily convert an Infix mathematical expression to a Postfix one? Well, the Shunting-yard algorithm is here for us! And thanks to Wikipedia, we have a pseudo-code representation of the algorithm!
Perfect, now that I knew where to start, there was another issue: how to read that thing? I will give you an example:
infix = 1 + 2 - (5 + 2 * 4)
rpn = 1 2 + 5 2 4 * + -
Yeah I know - it looks like a big mess at first sight but I will tell you how to convert and read it by hand and you'll see, it's pretty easy.
Conversion
To convert from infix to RPN, we'll need 2 stacks: one is the output, the other one is the operator stack. We'll symbolise everything in array-style:
input = [1, +, 2, -, (, 5, +, 2, *, 4, )]
output = []
operators = []
We have 2 rules:
- literals always goes to the output stack
- when an operator with lower or equal precedence than the last element of the operators stack is comming, pop the last element of the operators stack to the output stack
Let's convert it!
First we have 1, a literal, like said in the rules above, it goes to the output stack:
input = [+, 2, -, (, 5, +, 2, *, 4, )]
output = [1]
operators = []
Then we encounter an operator so, in the operators stack it goes!
input = [2, -, (, 5, +, 2, *, 4, )]
output = [1]
operators = [+]
Again, we face a literal so we put it in the output stack:
input = [-, (, 5, +, 2, *, 4, )]
output = [1, 2]
operators = [+]
After that, we have an operator that have the same precedence than the last operator in the operators stack which means that the actual + will be poped into the output stack and we will push the - to the operators stack:
input = [(, 5, +, 2, *, 4, )]
output = [1, 2, +]
operators = [-]
Parentheses doesn't have precedence in Infix notation but we put it in the operators stack to separate the enclosed expression until we find a closing parenthese:
input = [5, +, 2, *, 4, )]
output = [1, 2, +]
operators = [-, (]
Again, 5 is a literal:
input = [+, 2, *, 4, )]
output = [1, 2, +, 5]
operators = [-, (]
+ is an operator, since the last operator in the operators stack is an opening parenthese, we don't care and just push it in the stack:
input = [2, *, 4, )]
output = [1, 2, +, 5]
operators = [-, (, +]
2 is a literal:
input = [*, 4, )]
output = [1, 2, +, 5, 2]
operators = [-, (, +]
* is an operator with higher precedence than the last operator in the stack (+) so we just push it:
input = [4, )]
output = [1, 2, +, 5, 2]
operators = [-, (, +, *]
4 is a literal, at this point I think that you must have understand that all literals goes in the output stack:
input = [)]
output = [1, 2, +, 5, 2, 4]
operators = [-, (, +, *]
Then we find a closing parenthese which means that we'll pop every operators into the output stack until the opening parenthese (we completly delete the opening parenthese, we don't need it anymore):
input = []
output = [1, 2, +, 5, 2, 4, *, +]
operators = [-]
Since we doen's have any more elements in our input stack, we pop all the operators into the output stack:
input = []
output = [1, 2, +, 5, 2, 4, *, +, -]
operators = []
You did it! You completly converted an Infix notation into a RPN!
Here's a graphical representation of what we did:
Now if you're not already bored by the length of this post, we'll see how to calculate it.
Calculation
We have our beautiful RPN: [1, 2, +, 5, 2, 4, *, +, -] but now we want to calculate the mathematical expression to get its value. It's a lot simpler than it seems:
We'll base on a single variable, doesn't need more than that:
rpn = [1, 2, +, 5, 2, 4, *, +, -]
Then we need to find the first operator in the stack (starting to the first element which is 1 here). Once we found it, we'll fetch the literal before and the one before the one before:
left = rpn[i - 2]
right = rpn[i - 1]
operator = rpn[i]
In our case, left is 1, right is 2 and operator is +. Seems like we got all we need! Simply doing left + right will give us the result (3). Then we have our number and just put it in replacement for the left, right and operator:
rpn = [3, 5, 2, 4, *, +, -]
And we repeat. First operator is *, left is 2, right is 4, calculate and replace (2 * 4 = 8):
rpn = [3, 5, 8, +, -]
Again with the +, left is 5 and right is 8, 5 + 8 = 13:
rpn = [3, 13, -]
Next first operator is -, right is 3 and left is 13, 3 - 13 = -10:
rpn = [-10]
Since we doesn't have any other operators, the last number in the stack is the result, otherwise you did it wrong at some point.
So rpn[0] is our result, which is the result of 1 + 2 - (5 + 2 * 4) as we wanted. Yay!
Conclusion
Now that you learned a new mathematical notation, you can have fun with and build your own calculator or programming language that can properly resolve operator precedence.
What other mathematical expression do you know and why do you use them?
Twitter: @qtmsheep
Github: Nathanael Demacon
Top comments (2)
I Literally just did this account only to share my enormous gratitude to this amazing post of yours. The way you explained the algorithm was just perfect. Thank you so much, it really was helpful!:D
Glad that this post was useful :) Thanks you