Shunting yard algorithm for immediate evaluation

Question

Generally, programs which evaluate an infix mathematical expression use some variation of the Shunting Yard Algorithm to first translate the expression into Reverse Polish Notation, and then evaluate the Reverse Polish Notation to get a single final value.

My question is, is there some well-known algorithm that bypasses the INFIX -> RPN step, and just evaluates the initial infix expression in place, using some kind of recursive descent parsing?

Presumably, it might be useful when writing compilers or parsers to translate INFIX -> RPN. The RPN is sort of a "compiled form" of the expression (an AST), which can be more easily evaluated by a computer using a simple output stack. But, if you're just simply writing code that immediately translates an infix expression into a numeric output value, you might not have any use for caching the intermediate RPN form.

So, is there any well-known algorithm for parsing infix expressions WITHOUT first converting to RPN? Or is converting to RPN generally more efficient than any other approach?

If you need to evaluate an equation more than once RPN will a faster solution as you don't need to do so much processing. You can also modify the Shunting Yard Algorithm to produce an AST directly, which is handy if you want to do anything other than evaluate. — Salix alba, May 26 '14 at 10:40

score 7 · Accepted Answer · answered May 25 '14 at 17:41

You can easily modify the shunting-yard algorithm to immediately evaluate the expression as you go rather than building up an RPN representation. Specifically, whenever you would normally pop off an operator and two operands from the stacks, rather than appending those tokens to the output, instead just evaluate the expression and push the result back onto the operand stack. Finally, at the very end, evaluate the expression implied by the operator and operand stacks by popping off two operands, popping an operator, computing the result, and pushing it back onto the stack.

For example, to evaluate 3 * 4 + 2, you'd do the following:

Process 3:
  Operators  
  Operands    3

Process *:
  Operators   *
  Operands    3

Process 4:
  Operators   *
  Operands    3 4

Process +:
  Operators   +
  Operands    12

Process 2:
  Operators   +
  Operands    12 2

End of input:
  Operators   
  Operands    14

Hope this helps!

Shunting yard algorithm for immediate evaluation

1 Answers1