Evaluating Arithmetic Expressions Using Inverse Polish Notation (RPN)

A mathematical expression is usually expressed in infix notation. For evaluation purposes, we can change it to postfix (reverse Polish) notation (using algorithms such as Shunting-Yard ), and then evaluate postfix notation using the stack.

I found out that calculators use this technique, but do modern compilers use this today to evaluate arithmetic expressions? How effective is it or are other methods (or algorithms) used?

+4
source share
1 answer

To answer this question, let me focus on the concepts you mentioned, infix notation , Shunting-Yard and evaluation , and then relate them to compilation.

To get started, we usually need to understand how the computer processes the expression. The expression is converted to an abstract syntax tree (AST), which is then used to create the code. The process of converting a tree to code is changing, but walking through the AST is the same as evaluating the expression.

AST for 1 + 2:

  + / \ 1 2 

Postfix: 1 2 +

This is evaluated by visiting the left branch, 1 ,
visiting the right branch, 2 ,
and then apply the + operator to the two operands.

AST for 1 * 2 + 3 ^ 4:

  + / \ ^ * / \ / \ 3 4 1 2 

Postfix: 3 4 ^ 1 2 * +

This is estimated visiting the left branch 3^4 ,
then visiting his left branch 3 ,
then by visiting its right branch 4 ,
then visiting the operator, ^ , and evaluating 3^4 and holding it as the new left branch for `+ ', i.e. 81

then visiting the right branch 1*2 ,
then visiting his left branch 1 ,
then visiting his right branch 2 ,
then visiting the operator, * , and evaluating 1*2 and holding it as the new right branch for `+ ', i.e. 2

then visiting the + operator, and evaluating 81+2 and returning that as a result of 83

Now infix notation is syntactic sugar to make expressions easier to read for people. To help convert infix notation to AST, the transform algorithm needs to know the priority and associativity of the operators. The algorithm also uses the stack, which is one of the main keys of the Shunting Yard algorithm. Every tool that I know to convert an infix into an evaluation strategy uses a stack in some way.

While the compiler does not explicitly evaluate the expression that can be executed using the calculator application, the compiler converts the movement of the tree for evaluation to code that will transform the evaluation.

Note. Since I do not know each compiler for each language, I can give you an answer based on general concepts. There is no rule that requires them, and I would not be surprised if some compilers skip AST and move from input code to compiled code without using AST.

Also, since you mention the compiler, I was only talking about compiled code and not about scripting languages.

Now, to get back to your questions:

Today, modern compilers use this for arithmetic expression evaluation?

I would not specifically use the Shunting Yard algorithm, but the concept of using the stack, which is one of the key concepts of the algorithm that I would use. You can choose for yourself if using the concepts of the algorithm is the same as using the algorithm.

Is this efficient enough or are other methods (or algorithms) used?

Hope you now know the answer to this question. The important thing is not the Shunting Yard algorithm, but the concept of using the stack to translate infix notation, which is important, and this is what is used with compilers. Remember that compiled languages ​​usually do more than evaluate expressions, they work with types, express a conditional expression of a process, store values, and create higher types such as methods / functions, classes, and modules.

+6
source

All Articles