i have been trying to write code for creating an infix tree for the given infix expression.
but i struck at writting the procedure itself.
suppose my expression is :
a + b *c + d
this is how the compiler evaluates
( ( a + ( b * c ) ) + d )
i am following the below procedure
scan each character and if its not " )" push it on to the stack.(please suggest me is it the correct way, getting tuff when you write the code)
when ever i found a " )" i will pop the characters from the stack and check if its an opearator if its an operator i will create the node with operator as root -> info
other wise
nodes with info as characters with left and right child NULL
( but how to decide what to add as left and right child with the root node )
for example
at first the stack is
c
*
b
(
+
a
(
after poping whenwe find the ")" the stack is
+
a
(
my confusion here is to how
to decide the terminating condition for pop and creating the tree from the sofar poped values ( i can use the condition like chatacter is not equal to ")" but still confusion)
this is what the tree should look like after creation.
+
+ d
a *
b c
for example this is how my stack looks like when we find the first
" )"
c
*
b
(
+
a
(
so here i pop c * b and i create
*
b c
and push this node on to the stack of nodes.
next i will pop the "(" so after this my stack has
+
a
(
till now we traversed
( a + ( b * c)
now we find another ")".
this is where i am struck because there are two possibilities
one is
+
+ d
* a
b c
which is incorrect
and the other is
+
+ d
a *
b c
this is correct
how will i decide where to add a and other previous node ( either left or right ).
i believe that i am getting confused about how to store the nodes and expression in the stack and related push and pop operations.
please suggest me what is the correct procedure to follow and related push and pop operations.
the program should work for both the paranthseized expressions and non paranthesized.
please reply me with some good source, after a lot of struggle i am posting this post.