Invisible <voi### [at] devnull> wrote:
> But how do you "decide" when the brackets can or can't be omitted?

  If you have the expression in a parsing tree, then that's trivial:

  When printing out the current node (which is an operator), if a child
node has a lower operator precedence, then print that child node in
parentheses. If the child node has a higher precedence, then you can
omit the parentheses.

  An example (you'd better use a fixed-width font):

      +
     / \
    3   *
       / \
      4   5

  When printing this tree, you start with the root node, ie. the '+'.
Since the root node has no parent, it doesn't need to be printed in
parentheses.

  Now you recurseively print the left subtree and the right subtree.
The left subtree is not an operator, and thus doesn't need parentheses.
It can be printed as-is. The right subtree is an operator: '*'. Since
'*' has a higher precedence than '+', you don't need to print parentheses
around it. Recursively print the subtrees of this '*' node, and you are done.
You get:

    3+4*5

  Another example:

      *
     / \
    3   +
       / \
      4   5

  This time when printing the right subtree you notice that '+' has a lower
precedence than '*'. Thus you need to print parentheses around it. Otherwise
everything is the same. Thus you get:

    3*(4+5)

  If a child node has the *same* precedence as the current node, that's
more interesting. Now it depends on whether the operator is associative
or not, and if not, which side of the current node it is. For example
'+' is associative and thus if it has a child node which is also '+',
that child node does not need parentheses. However '-' is not associative,
and if it's the right child node of '+' (or '-'), it requires parentheses.

-- 
                                                          - Warp

Post a reply to this message