DEV Community

Cover image for How calculators read mathematical expression with operator precedence
Nathanael Demacon
Nathanael Demacon

Posted on • Updated on

How calculators read mathematical expression with operator precedence

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 * + -
Enter fullscreen mode Exit fullscreen mode

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 = []
Enter fullscreen mode Exit fullscreen mode

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 = []
Enter fullscreen mode Exit fullscreen mode

Then we encounter an operator so, in the operators stack it goes!

input = [2, -, (, 5, +, 2, *, 4, )]

output = [1]
operators = [+]
Enter fullscreen mode Exit fullscreen mode

Again, we face a literal so we put it in the output stack:

input = [-, (, 5, +, 2, *, 4, )]

output = [1, 2]
operators = [+]
Enter fullscreen mode Exit fullscreen mode

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 = [-]
Enter fullscreen mode Exit fullscreen mode

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 = [-, (]
Enter fullscreen mode Exit fullscreen mode

Again, 5 is a literal:

input = [+, 2, *, 4, )]

output = [1, 2, +, 5]
operators = [-, (]
Enter fullscreen mode Exit fullscreen mode

+ 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 = [-, (, +]
Enter fullscreen mode Exit fullscreen mode

2 is a literal:

input = [*, 4, )]

output = [1, 2, +, 5, 2]
operators = [-, (, +]
Enter fullscreen mode Exit fullscreen mode

* 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 = [-, (, +, *]
Enter fullscreen mode Exit fullscreen mode

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 = [-, (, +, *]
Enter fullscreen mode Exit fullscreen mode

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 = [-]
Enter fullscreen mode Exit fullscreen mode

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 = []
Enter fullscreen mode Exit fullscreen mode

You did it! You completly converted an Infix notation into a RPN!
Here's a graphical representation of what we did:
Shunting-yard algorithm

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, *, +, -]
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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, *, +, -]
Enter fullscreen mode Exit fullscreen mode

And we repeat. First operator is *, left is 2, right is 4, calculate and replace (2 * 4 = 8):

rpn = [3, 5, 8, +, -]
Enter fullscreen mode Exit fullscreen mode

Again with the +, left is 5 and right is 8, 5 + 8 = 13:

rpn = [3, 13, -]
Enter fullscreen mode Exit fullscreen mode

Next first operator is -, right is 3 and left is 13, 3 - 13 = -10:

rpn = [-10]
Enter fullscreen mode Exit fullscreen mode

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

Oldest comments (2)

Collapse
 
deckermv profile image
DeckerMV

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

Collapse
 
quantumsheep profile image
Nathanael Demacon • Edited

Glad that this post was useful :) Thanks you