Is it custumary to convert from infix to postfix and then build an AST on math evaluators?

user_9615454 0
Viewed 1351

I'm doing a mathematical expressions parser that parses text into an abstract syntax tree (and I don't know much about doing so).

I've read on Wikipedia that one can use the Shunting-yard algorithm to parse a linear sequence of tokens into Reverse Polish notation or into an AST on itself, but I was not able to find any examples of direct infix-to-AST parsing with Shunting-yard.

Right now I'm using Shunting-yard to convert from infix to postfix notation and then using such output to build an AST.

Is it good practice to convert the expression to postfix notation and then build an AST from it or am I being a bit clumsy?

evaluation math parsing
1 Answers

To make the shunting yard directly produce an AST the output should be changed to a stack of nodes.

When a number, variable or other terminal is encountered in the input, this is converted to a leaf node, and pushed to the output stack. When an operator is encountered its pushed on to the operator stack as normal.

The biggest change is what happens when an operator is popped off the operator stack. If its a binary operator then last two nodes on the output stack are popped off, an new binary node is constructed with these nodes as children and pushed back on the output stack.

In psudo code

Stack<Node> output
Stack<Operator> operators

function popOperator
    Operator op = operators.pop()
    Node right = output.pop()
    Node left = output.pop()
    Node n = makeNode( op, left, right )
    output.push(n)
user_8654810
Related