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.

2
Contributors
2
Replies
3
Views
8 Years
Discussion Span
Last Post by Gaiety

Wait how is that incorrect?

It doesn't matter which order you add something, that result is still the same. -associative property?

Wait how is that incorrect?

It doesn't matter which order you add something, that result is still the same. -associative property?

suppose if the following expression is considered

( ( ( a / b ) * c ) * d )

then i will write two forms

*
*           d
/         c
a           b

if you traverse in the inorder fashion
you will get the same expression
i.e a / b * c * d
i believe that is correct.

but if i follow the second method

*
d           *
c         /
b           a

now traverse in the pre order fashion
d * c * b / a

which is evaluated as
( ( ( d * c ) * b) / a)

if you assume the values of a , b, c and d as 10, 5, 7 and 8
the first will generate 112
and the second will generate 21.

i just believe this is what happens when you do not attach the subtrees properly.

please correct me if i am wrong in my anology.

i am creating nodes when ever i find a close parenthesis
but getting confused on how to attache the sub trees and when to stop.
please suggest me a good precedure

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.