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?
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!