Make a Binary tree from Infix expression

Program
Make a Binary tree from Infix expression.


Infix :-> 4 $ 2 * 3 - 3 + 8 / 4 / (1 + 1)


Solution: First separate the operator and operand
___________________________________________________________


Operator:-> $ * - + / / (+)


Operand:-> 4 2 3 3 8 4 1 1
___________________________________________________________


Now separate the operator according to their priority


First priority :-> ( + ) // Because ( ) has greater priority


Second priority :-> $


Third priority :-> * / /


Fourth priority :-> - +
_____________________________________________________
Step 1:
_____________________________________________________


Root will be fixed according to lowest priority


So, In Foruth priority - +


Here + will be the first root of tree (right to left)


+
_________________________________________________
Step 2:
_________________________________________________




Now - will be the left child of root of this tree


Because - is existing in left side of +.


+
/
/
-


_________________________________________________
Step 3:
_________________________________________________


Now in Third priority :-> * / /


Here / will be right child of +.


Because / is existing in right side of +.
+
/ \
/ \
- /


_________________________________________________
Step 4:
_________________________________________________


Here / will be right child of /.


Because / is existing in left side of /.
+
/ \
/ \
- (/) Devide sign (no 1)
/
/
(/) devide sign (no 2)


_________________________________________________
Step 5:
_________________________________________________
Here * will be left child of -.


Because, In infix expression, * is existing in left side of -.


+
/ \
/ \
- (/) Devide sign (no 1)
/ /
/ /
* (/) devide sign (no 2)


_________________________________________________
Step 6:
_________________________________________________


In Second priority:-> $


Here $ will be left child of *.


Because, In infix expression,


$ is existing in left side of *.


+
/ \
/ \
- (/) Devide sign (no 1)
/ /
/ /
* (/) devide sign (no 2)
/
/
$
_________________________________________________
Step 7:
_________________________________________________


In First priority:-> (+)


Here (+) will be left child of / (devide sign no 1).


Because, In infix expression,


$ is existing in left side of *.


+
/ \
/ \
- (/)
/ / \
/ / \
* (/) +
/
/
$


_________________________________________________
Step 8:
_________________________________________________


Now As we know the expression is


Infix :-> 4 $ 2 * 3 - 3 + 8 / 4 / (1 + 1)


Operand:-> 4 2 3 3 8 4 1 1


Now put the operand only


_____________________________________________________


First of all take 4, Here 4 will be left child of $.


Because 4 is left side of $ in expression


+
/ \
/ \
- (/)
/ / \
/ / \
* (/) +
/
/
$
/
/
4
_____________________________________________________


Now take 2 , Here 2 will be right child of $.


Because 2 is right side of $ in expression.


+
/ \
/ \
- (/)
/ / \
/ / \
* (/) +
/
/
$
/ \
/ \
4 2
_____________________________________________________


Now take 3 , Here 3 will be right child of *.


Because 3 is right side of * in expression.


+
/ \
/ \
- (/)
/ / \
/ / \
* (/) +
/ \
/ \
$ 3
/ \
/ \
4 2


_____________________________________________________


Now take 8, Here 8 will be left child of /(devide sign no 2).


Because 8 is left side of / in expression. Here i am not saying that 8 will be right child of +. Because / is the right child of +. And operand won't be root in Tree. So i am taking Here 8 will be left child of /(devide sign no 2).


+
/ \
/ \
- (/)
/ \ / \
/ \ / \
* 3 (/) +
/ \ /
/ \ /
$ 3 8
/ \
/ \
4 2


________________________________________________________


Now take 4, Here 4 will be right child of /(devide sign no 2).


Because 4 is right side of / in the given expression.


+(first +)
/ \
/ \
- (/)
/ \ / \
/ \ / \
* 3 (/) + (second +)
/ \ / \
/ \ / \
$ 3 8 4
/ \
/ \
4 2


________________________________________________________


Now take 1, Here 1 will be left child of + (second +).


Because 1 is right side of /(devide sign no 2) in the given expression.


+ (first +)
/ \
/ \
- (/)
/ \ / \
/ \ / \
* 3 (/) + (second +)
/ \ / \ /
/ \ / \ /
$ 3 8 4 1
/ \
/ \
4 2




________________________________________________________


Now take 1, Here 1 will be right child of + (second +).


Because 1 is right side of + (second +) in the given expression.


+
/ \
/ \
- (/)
/ \ / \
/ \ / \
* 3 (/) +
/ \ / \ / \
/ \ / \ / \
$ 3 8 4 1 1
/ \
/ \
4 2


-------------------------------------------
The final Tree for an expression |
|
Infix :-> 4 $ 2 * 3 - 3 + 8 / 4 / (1 + 1) |
|
-------------------------------------------
|
+ |
/ \ |
/ \ |
- (/) |
/ \ / \ |
/ \ / \ |
* 3 (/) + |
/ \ / \ / \ |
/ \ / \ / \ |
$ 3 8 4 1 1 |
/ \ |
/ \ |
4 2 |
|
-------------------------------------------