GATE CSE
First time here? Checkout the FAQ!
x
0 votes
132 views

If we have to construct the expression tree from this expression (3 + ((5+9)*2)) then what will be the order of push and pop operation on a stack ?Explain what to do with each operator and operand along the way of push and pop operation

asked in DS by Veteran (42.1k points)   | 132 views
to make expression tree first of all we need to convert infix expression to postfix expression.

For above infix - (3 + ((5 + 9 ) * 2 ) )

               postfix - 3 5 9 + 2 * +

now after getting postfix expression do following operation -

1. traverse postfix expression from start '3' to the last '+' operator/operand.

2. If it is operand than make a new node and make its data part to the operand and make its both child points to null and push the node into the stack.

3. if it is operator then first of all make new node and make its data part to the incoming operator and do two pop operation and make first popped node right child of the new node and second popped node to the left child of the new node and finally push the new node(containing operator as data part of node) into the stack.
I'm not getting can be explain more..what is meaning of order and why we need to convert first into postfix
@vijay i did as you said initially 3 5 9 has been pushed onto the stack after that i encountered first operator for that i made  2 node first for 9 which will be right node and second for 5 as left node and i made "+" as parent of both

now next we got 2 which i operand i pushed it on to the stack  at this point we have 3 and 2 in stack now again we got  * a operator now problem is for this operator should i pop both 3 and 2 and make then node and parent as * or should i pop only 2 .

if both then what will be the position of both in expression tree and if one then why only one ?
@chauhan check once how they created tree. https://en.wikipedia.org/wiki/Binary_expression_tree
@Tauhin Thanks this link has cleared mu doubt ...i was looking at a different website that has not explained it so well.
@sekhar .. I had forgotten one more thing to mention there in 3rd step -- after making left and right child .. now we need to push that node(parent node) containing operator as data part of node into the stack.

its okay i got it .yes

Is it any rule that first poped node become right child of new node and second popped node become left child of new node.

I think it depend upon the the operater associativity who cause two pop from stack.

If incomming operator is left associativity then first poped node become right child of new node and second popped node become left child of new node.

If incomming operator is right associativity then first poped node become left child of new node and second popped node become right child of new node.

let me know am i correct?

1 Answer

+2 votes

this is basic idea, if we want to implement it we can modify accordingly

answered by Active (2.2k points)  


Top Users May 2017
  1. akash.dinkar12

    3338 Points

  2. pawan kumarln

    2066 Points

  3. Bikram

    1922 Points

  4. sh!va

    1672 Points

  5. Arjun

    1614 Points

  6. Devshree Dubey

    1272 Points

  7. Debashish Deka

    1174 Points

  8. Angkit

    1056 Points

  9. LeenSharma

    1018 Points

  10. Arunav Khare

    758 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. Bikram

    1008 Points

  2. pawan kumarln

    692 Points

  3. Arnab Bhadra

    632 Points

  4. Arjun

    342 Points

  5. bharti

    328 Points


22,888 questions
29,193 answers
65,292 comments
27,691 users