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

1. ## 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.

2. ## 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

3. ## 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).

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

Originally Posted by Induction
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.