Results 1 to 4 of 4
Like Tree2Thanks
  • 1 Post By SlipEternal
  • 1 Post By SlipEternal

Thread: Trouble converting this postfix expression to an infix expression (expression trees)

  1. #1
    Newbie
    Joined
    Sep 2017
    From
    Around.
    Posts
    13

    Exclamation Trouble converting this postfix expression to an infix expression (expression trees)

    Trying to convert the following postfix expression into an infix expression...

    A B + C D x E F / - - A x

    Note, this is for a binary tree.

    Having a lot of trouble interpreting this question. Firstly, I'm trying to draw this binary tree. The top root will be "x" (far-right operator in this postfix expression); however, I'm not sure how to group the left child and right child from here.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,834
    Thanks
    1087

    Re: Trouble converting this postfix expression to an infix expression (expression tre

    Let's break it down:
    A B + means (A + B)
    (A + B) C D x means (A + B) (C x D)
    (A + B) (C x D) E F / means (A + B) (C x D) (E / F)
    (A + B) (C x D) (E / F) - means (A + B) [(C x D) - (E / F)]
    (A + B) [(C x D) - (E / F)] - means [(A + B) - [(C x D) - (E / F)]]
    [(A + B) - [(C x D) - (E / F)]] A x means [(A + B) - [(C x D) - (E / F)]] x A, which is the final infix expression.

    Converting to a binary tree - See image
    Attached Thumbnails Attached Thumbnails Trouble converting this postfix expression to an infix expression (expression trees)-decision_tree.png  
    Thanks from Induction
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2017
    From
    Around.
    Posts
    13

    Re: Trouble converting this postfix expression to an infix expression (expression tre

    Excellent. This was NOT what I was shown. Breaking it down into parts and going to infix form for the separate parts.

    The way I saw was like the opposite way. Trying to build the left child and right child from the top of the tree... instead of going left to right (reading the expression) and converting the smaller parts to infix (as you've done).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,834
    Thanks
    1087

    Re: Trouble converting this postfix expression to an infix expression (expression tre

    Quote Originally Posted by Induction View Post
    Excellent. This was NOT what I was shown. Breaking it down into parts and going to infix form for the separate parts.

    The way I saw was like the opposite way. Trying to build the left child and right child from the top of the tree... instead of going left to right (reading the expression) and converting the smaller parts to infix (as you've done).
    The idea of postfix notation is that you can read it from left to right. As you read, you develop a stack of numbers. You need at least two numbers on the stack. When you encounter an operator, you pop two numbers from the stack and apply the operator where the first number popped goes on the right of the operator and the second number popped goes on the left. So, when adding A B + C D x E F / - - A x to the stack, it looks like this:

    Push A to stack - Stack: A
    Push B to stack - Stack: A, B
    Pop B from stack - Stack: A
    Pop A from stack - Stack:
    Add A + B and push new value to stack - Stack: (A + B)
    Push C to stack - Stack: (A + B), C
    Push D to stack - Stack: (A + B), C, D
    Pop D from stack - Stack: (A + B), C
    Pop C from stack - Stack: (A + B)
    Multiply C x D and push to stack - Stack: (A + B), (C x D)
    Push E to stack - Stack: (A + B), (C x D), E
    Push F to stack - Stack: (A + B), (C x D), E, F
    Pop F from stack - Stack: (A + B), (C x D), E
    Pop E from stack - Stack: (A + B), (C x D)
    Divide E / F and push to stack - Stack: (A + B), (C x D), (E / F)
    Pop (E / F) from stack - Stack: (A + B), (C x D)
    Pop (C x D) from stack - Stack: (A + B)
    Subtract (C x D) - (E / F) and push to stack - Stack: (A + B), [(C x D) - (E / F)]
    Pop [(C x D) - (E / F)] from stack - Stack: (A + B)
    Pop (A + B) from stack - Stack:
    Subtract (A + B) - [(C x D) - (E / F)] and push to stack - Stack: [(A + B) - [(C x D) - (E / F)]]
    Push A to stack - Stack: [(A + B) - [(C x D) - (E / F)]], A
    Pop A from stack - Stack: [(A + B) - [(C x D) - (E / F)]]
    Pop [(A + B) - [(C x D) - (E / F)]] from stack - Stack:
    Multiply [(A + B) - [(C x D) - (E / F)]] x A and push to stack - Stack: [(A + B) - [(C x D) - (E / F)]] x A

    What you wind up with on the stack is the final infix form. I am basically processing it how a calculator would process it.
    Thanks from Induction
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: Nov 5th 2014, 12:01 PM
  2. Help with postfix expression problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Apr 27th 2014, 06:17 PM
  3. Replies: 1
    Last Post: Nov 29th 2012, 03:59 PM
  4. Replies: 5
    Last Post: May 1st 2012, 09:54 AM
  5. Replies: 6
    Last Post: Oct 6th 2011, 01:48 PM

/mathhelpforum @mathhelpforum