# Algorithm to go from infix notation to a tree

I've been trying to figure out an algorithm to go from an infix equation to a syntax tree, like so:

`(1+3)*4+5`

``````      +
*   5
+   4
1 3
``````

However, I don't just want it to handle operators, I want it to handle functions with arbitrary argument numbers as well, i.e:

`max(1,3,7)*4+5`

``````      +
*   5
max  4
1 3 7
``````

Here's the general algorithm I've come up with:

You start with the root node of the tree, containing a `null` value. You have a pointer which moves around the tree as you parse the expression, and starts pointed at the root node.

There are also some aspects of the tree I should probably clarify:

1. Inserting at a node means adding to the end of the node's children.
2. Injecting at a node means adding to a specific index in the node, and removing the node at that index and inserting it to the injected node. So, if node `A` has child `B` at index 0, and we inject node `C` at index 0, node `A` will have a child `C` which will have a child `B`.
3. Replacing at an index removes the node at that index and puts the alternate node in its stead. So if we have node `A` with child `B` at index 0, and we replace using `C` at index 0, we will have node `A` with child `C`.

Ok, so here's the algorithm so far.

For every token in the infix string:

• if the token is a number
• insert it as a child of the current node
• if the token is an argument separator
• traverse up the tree until the value of your current node is a function
• if the token is a left parenthesis
• if the value of the current node is not a function, insert our token as a child node, and set our current node to the token's node.
• if the token is a right parenthesis
• traverse until the current node is either a left parenthesis or a function
• if the current node is a left parenthesis, replace it with its first child (index 0). This is equivalent to removing the parenthesis node from the tree structure, while keeping its first child intact.
• traverse up one level, to the parent of the current node
• if the token is a function
• insert the token as a child node of the current node, and set the current node to the newly inserted child node
• if the token is an operator
• if the current node is not a left parenthesis or the root node
• traverse up if
• the current node is not at the root, or
• the token is right associative and the precedence of the token is less than the precedence of the current node or
• the token is left associative and the precedence of the token is less than or equal to the precedence of the current node
• inject the token as a new node at the last index of the current node
• set the current node to its newly added token child node

Once you have gone through all the tokens, return the first child of the root node.

Is there an existing algorithm I can check this against? Are there any obvious problems with this? Are there any particularly difficult to parse problems I can plug in using this and see if they work?

• You may be interested in the shunting yard algorithm. – Ixrec Jul 22 '15 at 23:24
• @Ixrec I actually started out using that. However, I didn't like the fact that you had to know exactly how many arguments you are passing to a function. Shunting-yard, as described by wikipedia, simply won't work when you have variable-argument functions, unless inside the function you specify your argument number, like `max(1,2,3 @3)` or something. This is pretty ugly and why I moved to a syntax tree. Right now I'm calling it shunting-tree... although there is probably already a named algorithm that does this I just haven't found. – MirroredFate Jul 22 '15 at 23:32

Treat the comma as an infix operator. Then

``````max(1,3,7)*4+5
``````

becomes

``````        +
/ \
*   5
/ \
max  4
|
,
/ \
,   7
/ \
1   3
``````

The comma should have a lower precedence than your calculation operators (+ - * / etc.).

• Ok, that's an interesting notion. Why? – MirroredFate Jul 23 '15 at 18:02
• Different approach - apply the function on two arguments and two arguments again. `max(1,2,3)` gets changed to `max(1,(max(2,3))` – user40980 Jul 23 '15 at 19:15
• 1: You already have the mechanics in place for parsing binary operators. 2: Standardizes the number of children a node can have so that walking the tree is simpler. – A. I. Breveleri Jul 24 '15 at 3:22
• @ MichaelT: Good idea but only works if the function composes its arguments associatively. It wouldn't work for eg. conditional( boolean, trueValue, Falsevalue ) or substring( string, count, start ) etc. – A. I. Breveleri Jul 24 '15 at 3:25

At some point you just need to graduate to a proper parser, because there are too many things to track and too many boundary cases. Adding function calls to the peg.js example grammar, you get.

``````primary
= integer
``````max(3+4,min(6,(1+2)*3))+2