|
![](/i/fill.gif) |
Warp wrote:
> If you have the expression in a parsing tree, then that's trivial:
I knew somebody round here would know the answer...
> 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)
Hmm. OK.
So... maybe when printing out any given subtree, I make the print
function take the precedence of the parent node as an extra argument?
(And omit brackets at the top-level by starting the function with an
infinitely low precedence?)
> 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.
Ah yes, associativity is a maddening thing. ;-)
Post a reply to this message
|
![](/i/fill.gif) |