Create recursive binary tree?

Question

I have two stacks, one with operands, the other with operators. My problem is turning these two stacks into a binary tree.

For example, the expression (2+3)*(4-3) will be translated into postfix ( such that 24+43-*) and then put into two stacks 3442 and *-+ will be the stacks (with the tops being 3 and * respectively).

Now with these stacks, i need to form a binary tree like

   *
 +    -
2 3  4 3

Is there a way to do this recursively?

Right now, I have an algorithm like so:

Create the root of the tree, assign the value of the root to the first operator in the operator-stack. Set the right and left pointers to null.
Create the right node, assign the value of the next operator if it exists, if not assign it an operand. Then do the same for the left node.

My problem is making this recursive, or getting it to handle the many different cases.

Thanks for your help.

you messed up the number stack slightly. Answer from Let_Me_Be below looks good, do you need more detail? — jon_darkstar
– jon_darkstar, Commented Nov 11, 2010 at 15:28
more detail would be nice. specifically, i can find the highest operator, but im not sure how to split the expression or 'apply on both parts'. — Blackbinary
– Blackbinary, Commented Nov 11, 2010 at 15:30
your method seems flawed: it requires that there are the same number of operands and operators on each side of an operator. using this expression (2+3)-4 results in a stack identical to 2+(3-4). — Adrien Plisson
– Adrien Plisson, Commented Nov 11, 2010 at 15:33
Your description doesn't seem to be unique. For instance, given the stacks 4321 and *-+, can you tell whether that should be (1+2)*(3-4) or ((1+2)-3)*4? — Chowlett
– Chowlett, Commented Nov 11, 2010 at 15:34

Jan · Accepted Answer · 2010-11-11 15:35:18Z

2

assuming you have only binary operators

treeNode createNode(operators, operands) {
  // take first operator and create a new treeNode with it. pop it from the operators stack 

  // if it is the last operator in the list then there should be only two operands left in the operands and you can assign them to the left and right child of the treeNode. return this treeNode.

  // if it is not the last operator then split the operands in two stacks equally
  // leftOperands and rightOperands
  // left child becomes createNode(operators, leftoperands)
  // right child becomes createNode(operators, rightoperands)
  // return this treeNode

}

answered Nov 11, 2010 at 15:35

Jan

8,1803 gold badges41 silver badges67 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Blackbinary Over a year ago

I am unsure how to split my stack of operands. I assume i will need to find the # of operands some way? What if its odd, does it matter which gets more operands?

Jan Over a year ago

I was assuming you have only binary operators so you would have a power of two # of operands. I am not sure if my algorithm will work. You should see it as how I would have approached this problem, it may contain loopholes. Success!

Blackbinary Over a year ago

Ah that is correct, forgot it could not be odd in this case. Thanks, i'll give it a try.

shinzou Over a year ago

Powers of 2 number of operands? what about ((1+2)*3)?

Šimon Tóth · Accepted Answer · 2010-11-11 15:26:05Z

1

Recursive algorithm:

find the highest priority operator
split the expression around this operator
recursively apply on both parts

answered Nov 11, 2010 at 15:26

Šimon Tóth

36.7k21 gold badges116 silver badges154 bronze badges

4 Comments

Adrien Plisson Over a year ago

apply this method with a stack of 24+43*- (which corresponds to (2+4)-(4*3)) and see the result...

Blackbinary Over a year ago

See my comment above, I'd like some further details. Thanks.

Šimon Tóth Over a year ago

@Adrien I missed the postfix part. This algorithm is for infix format.

Šimon Tóth Over a year ago

@Blackbinary I was talking about infix format. x+y*z would be split around * into x+y and z.

Adrien Plisson · Accepted Answer · 2010-11-11 15:39:00Z

0

if your expression is always symmetrical (the same number of operands and operators on each side of an operator), then the method you describe works fine, with a little modification:

create a node, assign the value of the top operator in the operator stack.
if there are no operator left on the operator stack, pop the 2 operands from the operands stack and assign them to the left and right branch, then exit
if there are any operator on the stack, go to the left brach of your node and call your algorithm, then go to the right branch and call your algorithm.

(Jan explained it so much clearer in his answer...)

answered Nov 11, 2010 at 15:39

Adrien Plisson

23.4k7 gold badges45 silver badges76 bronze badges

1 Comment

Blackbinary Over a year ago

I'm going to assume it is always symmetrical. I will try your approach. Thanks for the help.

vonbrand · Accepted Answer · 2013-01-20 00:59:21Z

0

In general there isn't a way of doing this. Does "1 2 3 4" "* + /" mean "1 2 3 4 * + /" (that is, "1 / (2 + 3 * 4)") or "1 2 * 3 + 4 /" , (that is "(1 * 2 + 3) / 4").

answered Jan 20, 2013 at 0:59

vonbrand

11.9k8 gold badges36 silver badges54 bronze badges

Collectives™ on Stack Overflow

Create recursive binary tree?

4 Answers 4

4 Comments

4 Comments

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

4 Comments

4 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related