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?
I had a similar project, and this is how I did it:
Tokenize the string. See what each symbol is. For example, the list may contain:
'(' Open parantheses '11' Number '+' Operator etc
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).
Evaluate the postfix expression. You can do it in two ways, a binary tree and stack.
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.
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.
This is the method I would use. Maybe there are more efficient methods than this, but this is how I would do it.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With