Create Binary Tree from Mathematical Expression

Question

I have a expression like ((2+8)*8)-(5*(5+2)) Or + 2 + 1 1 . And I want to make a binary tree in that .

  +
 / \
2   +
   / \
  1   1

How can I Make this Binary tree?

Answer 1

I had a similar project, and this is how I did it:

1. Tokenize the string. See what each symbol is. For example, the list may contain:

   '(' Open parantheses
   '11' Number
   '+' Operator etc

2. Convert the expression to postfix (or prefix if you want) notation. One algorithm that can do that is called the Shunting Yard algorithm. The advantage of postfix notation is that you can evaluate the expression much easier, using a stack-based method (or binary tree if you want).

3. Evaluate the postfix expression. You can do it in two ways, a binary tree and stack.

Stack evaluation:

Your example expression converted in postfix notation will look like this:

2 8 + 8 * 5 5 2 + * -

Evaluating works like this: When you encounter a number, push it on the stack. When you encounter an operator, pop 2 items from the stack, make the calculation, and push the result on the stack. In the end, you should be left with the final result.

For the example above, this is what we will do:

Push 2 [Stack content: 2]
Push 8 [2 8]
Pop 2 and 8 []
Push 2+8 [10]
Push 8 [10 8]
Pop 10 and 8 []
Push 10*8 [80]
Push 5 [80 5]
Push 5 [80 5 5]
Push 2 [80 5 5 2]
Pop 2 and 5 [80 5]
Push 2 + 5 [80 5 7]
Pop 7 and 5 [80]
Push 7 * 5 [80 35]
Pop 80 and 35 []
Push 80 - 35 [45]
Final result is 45.

Binary tree

This is how I would do it: just like the stack based approach, use a stack of nodes. When you encounter an operator, you pop 2 items from the stack, but instead of evaluating, you create a node with the operator, and make it the parent of the 2 popped items. Then you push the node back on the stack.

The disadvantage of this approach is that you have an additional step: creating the tree.

Final notes

This is the method I would use. Maybe there are more efficient methods than this, but this is how I would do it.