2

I'm doing a homework assignment where I'm supposed to look at trees to find the expression, and build my own trees based on expressions, but I'm a little confused about how negative numbers are used. The first problem on the assignment is to find the expression for this tree: first parse tree

To me, this looks like a poorly made tree, since if you use in-order traversal, you end up with this: X*(50/y)-*(z-36). Does that negative sign mean that the entire left branch is negative, like this?: -(x*(50/y))*(z-36).

It seems to me that it should be done like this: second parse tree

The expression here is (–(50*x)+y)/z, and it reads correctly with in-order traversal. Am I correct in thinking that my professor is wrong here?

Edit: I also have a question about another one of the trees made by my professor. This is the tree:

Third parse tree

I'm not sure what the extra + sign means on the far right side. It looks like the answer is (x-(y*80))-((z+4)+20), but since there are two plus signs, I'm not sure what the second one is supposed to do.

wipeout4wh
  • 35
  • 9
  • The second image doesn't look right to me. A node in a tree can only have one parent; in yours, "*" has two parents, "-" and "y". – Kevin Aug 07 '14 at 20:23
  • So is the first one correct? It doesn't really make sense to me to have the negative sign where it is, since the in-order traversal doesn't make sense. How to you show that 50x is negative without using two parent nodes? – wipeout4wh Aug 07 '14 at 20:27
  • 2
    I think the idea is that if you encounter a `-` operator with only 1 argument (child) then you just negate what you have so far. – mclaassen Aug 07 '14 at 20:29

1 Answers1

1

Your professor has it right. The expression consists of operators and numbers. Operators can be either binary (that is, they can take two arguments) as with a*b or unary as with -a. The first parse tree contains a unary operator - so the expression, with added parentheses for clarity would be this:

(-(x*(50/y)))*(z-36)

It might be easier to think of the expression as a series of operations, so we might have subtract(a,b) to represent the expression a-b. A unary operator, such as - might be something like negate(a) to represent the expression -a.

The expression can be derived from the tree, as you've mentioned, by doing an in-order traversal. Basically, the algorithm is to visit the left child, root then right child. If you modify that slightly by printing a '(' just before you visit each left child and then ')' after each right child, you'll get a fully parenthesized version of the original expression. In psuedo-code:

print '('
print left child
print parent 
print right child
print ')'

However, this doesn't work with unary operators, as you've discovered. The reason is that the convention we use for unary operators is to put them in front of the expression to which they apply, but it makes perfect sense if you've ever used an RPN calculator.

In the third tree you've shown, there is a unary '+' operator, so the lower right would be rendered as the number +20.

Edward
  • 6,964
  • 2
  • 29
  • 55
  • Thanks. Does that mean that the negative sign, when used by itself, basically means "take everything before this and make it negative"? In that case, does that mean that the minus sign in my second example should be moved between the * and + signs? Also, how does that work with + signs? Could you look at my edit for an example? – wipeout4wh Aug 07 '14 at 20:42
  • 1
    @wipeout4wh: I've edited my answer to try to answer those questions as well, but the simple answer to your first question in the comment is "yes, that's exactly what it means." – Edward Aug 07 '14 at 21:04
  • Thank you, but on the third tree, there are two plus signs before the 20, and the final plus sign only has one child node (20). It looks like maybe that was supposed to be a unary -, but he forgot to change it after he copied it? – wipeout4wh Aug 07 '14 at 21:10
  • 1
    @wipeout4wh: Ah, I had overlooked that, but you're right. I've updated my answer to address that. – Edward Aug 07 '14 at 21:16
  • Ok, thanks. Does that mean that in this specific example, it doesn't really do anything? Since 20 is already being added, and it's already a positive number, that seems to be unnecessary. I can see how it would be useful in other situations, though. If we had 2++1-6, am I correct in thinking that would mean 2+|1-6|? – wipeout4wh Aug 07 '14 at 21:24
  • @wipeout4wh: [Here](http://stackoverflow.com/questions/727516/what-does-the-unary-plus-operator-do) is a whole page full of thoughts on what unary + means. – Edward Aug 07 '14 at 21:33