2

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.

Blackbinary
  • 3,936
  • 18
  • 49
  • 62
  • you messed up the number stack slightly. Answer from Let_Me_Be below looks good, do you need more detail? – jon_darkstar Nov 11 '10 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 Nov 11 '10 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 Nov 11 '10 at 15:33
  • Can you give any advice then, Adrien? – Blackbinary Nov 11 '10 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 Nov 11 '10 at 15:34
  • Chris, i am keeping track of the brackets... but honestly i can't think of a way to make the two unique. – Blackbinary Nov 11 '10 at 15:37
  • @TED: ["The homework tag...is now discouraged,"](http://meta.stackoverflow.com/q/10812) but, @Blackbinary, please (as always and as you have been) continue to follow [general guidelines](http://tinyurl.com/so-hints): state any special restrictions, show what you've tried so far, and ask about what specifically is confusing you. You can mention in the text that it is homework, if you think that will give you better answers; but what's really important is the unique constraints that may apply to you depending on your school (the "special restrictions" in the list). –  Nov 11 '10 at 15:40
  • you absolutely have to mix the operands and operators on the same stack. use a union (if you are using a C based language) or variant record (if you are using a pascal based language) to store either an operand or an operator in each item of your stack. – Adrien Plisson Nov 11 '10 at 15:41
  • Thanks for the info Roger and Adrien, it is an assignment, but it is fairly vague. I'm going to assume the equations will always be balanced, since those are the tests cases we've been given. – Blackbinary Nov 11 '10 at 15:45

4 Answers4

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

}
Jan
  • 8,011
  • 3
  • 38
  • 60
  • 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? – Blackbinary Nov 11 '10 at 15:49
  • 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! – Jan Nov 11 '10 at 15:54
  • Ah that is correct, forgot it could not be odd in this case. Thanks, i'll give it a try. – Blackbinary Nov 11 '10 at 16:01
  • Powers of 2 number of operands? what about `((1+2)*3)`? – shinzou May 16 '15 at 11:01
1

Recursive algorithm:

  • find the highest priority operator
  • split the expression around this operator
  • recursively apply on both parts
Šimon Tóth
  • 35,456
  • 20
  • 106
  • 151
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").

vonbrand
  • 11,412
  • 8
  • 32
  • 52
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:

  1. create a node, assign the value of the top operator in the operator stack.
  2. 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
  3. 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...)

Adrien Plisson
  • 22,486
  • 6
  • 42
  • 73