Arithmetic Expression Evaluation using Reverse Polish Notation (RPN)

Question

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

I found out that calculators use this technique, but do today's modern compilers use this for arithmetic expression evaluation? Is it efficient enough or other techniques (or algorithms) are being used?

Answer 1

To answer this question let's focus on the concepts you mention, infix notation, Shunting-Yard and evaluation and then relate them to compiling.

To start with we need to understand typically how a computer processes an expression. An expression is converted to an abstract syntax tree (AST) which is then used to create the code. The process of converting the tree to code varies but a walk of 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,
the visiting the right branch, 2,
and then applying the operator, +, to the two operands.

AST for 1*2+3^4:

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

Postfix: 3 4 ^ 1 2 * +

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

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

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

Now infix notation is syntactic sugar to make using expressions easier to read for humans. In order to help convert infix-notation to an AST, the conversion algorithm needs to know the precedence and associativity of the operators. The algorithm also uses a stack which is one of the main keys to the Shunting-Yard algorithm. Every means I know of to convert infix to an evaluation strategy uses a stack in some way.

While a compiler does not explicitly evaluate an expression as can be done with a calculator application, the compiler does convert the walking of the tree for evaluation into code that will preform the evaluation.

Note: Since I do not know every compiler for every language, I can only give you an answer based on general concepts. There is no rule that requires these be followed and I would not be surprised if some compilers skip the AST and go from the input code to compiled code with out using AST.

Also since you mention a compiler I only talked about compiled code and did not touch on scripting languages.

Now to get back to your questions:

Do today's modern compilers use this for arithmetic expression evaluation?

I would not specifically use the Shunting-Yard algorithm but the concepts of using a stack which is one of the key concepts of the algorithm I would be using. You can chose for yourself if using the concepts of algorithm is the same as using the algorithm.

Is it efficient enough or other techniques (or algorithms) are being used?

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