Algorithm to go from infix notation to a tree

Question

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?

Answer 1

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.).

Answer 2

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
  / "(" additive:additive ")" { return additive; }
  / function_call

function_call
  = [a-z]+ "(" args ")"

args
  = (additive ("," additive)*)?

Note this easily handles boundary cases like function calls and expressions nested within function calls:

max(3+4,min(6,(1+2)*3))+2