 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
OK, so does anybody know the trick to taking a parse tree such as
(2*(5^2))+((8*6)^(x-1)))
and printing it out *without* several billion brackets?
Printing it with brackets as above, or with no brackets at all, is quite
trivial:
output expr = case expr of
Operator n x y = "(" ++ output x ++ n ++ output y ++ ")"
Variable n = n
Constant v = show v
...
But how do you "decide" when the brackets can or can't be omitted?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible <voi### [at] dev null> wrote:
> OK, so does anybody know the trick to taking a parse tree such as
>
> (2*(5^2))+((8*6)^(x-1)))
>
> and printing it out *without* several billion brackets?
>
> Printing it with brackets as above, or with no brackets at all, is quite
> trivial:
>
> output expr = case expr of
> Operator n x y = "(" ++ output x ++ n ++ output y ++ ")"
> Variable n = n
> Constant v = show v
> ...
>
> But how do you "decide" when the brackets can or can't be omitted?
Just a thought:
if the next operator up the tree defers (has lower precedence) to the current
operator, omit the brackets.
eg:
(2*(5^2))+((8*6)^(x-1))) + defers to * --> omit 2*(5^2)+((8*6)^(x-1)))
(2*(5^2)) : * defers to ^ --> omit (2*5^2)
(8*6)^(x-1): ^ doesn't defer to * or - --> don't omit
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> So... maybe when printing out any given subtree, I make the print
> function take the precedence of the parent node as an extra argument?
I'd to print the parens (if needed) in the parent call before recursing.
--
Darren New, San Diego CA, USA (PST)
My fortune cookie said, "You will soon be
unable to read this, even at arm's length."
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 12-3-2009 15:22, Invisible wrote:
> OK, so does anybody know the trick to taking a parse tree such as
>
> (2*(5^2))+((8*6)^(x-1)))
>
> and printing it out *without* several billion brackets?
>
> Printing it with brackets as above, or with no brackets at all, is quite
> trivial:
>
> output expr = case expr of
> Operator n x y = "(" ++ output x ++ n ++ output y ++ ")"
> Variable n = n
> Constant v = show v
> ...
>
> But how do you "decide" when the brackets can or can't be omitted?
Why not in (reverse) polish, no brackets at all
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
andrel wrote:
> Why not in (reverse) polish, no brackets at all
If you think *you* can find a suitable encoding for lambda expressions
in reverse polish notation, be my freakin' guest! :-P
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 13-3-2009 10:01, Invisible wrote:
> andrel wrote:
>
>> Why not in (reverse) polish, no brackets at all
>
> If you think *you* can find a suitable encoding for lambda expressions
> in reverse polish notation, be my freakin' guest! :-P
I'd say that polish would be enormously more simple than standard infix.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>>> Why not in (reverse) polish, no brackets at all
>>
>> If you think *you* can find a suitable encoding for lambda expressions
>> in reverse polish notation, be my freakin' guest! :-P
>
> I'd say that polish would be enormously more simple than standard infix.
Not once you add case expressions, let expressions, type signatures and
so forth.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
andrel wrote:
> Why not in (reverse) polish, no brackets at all
Fun thing:
12+3*
123+*
These two expressions look different, but are guaranteed to produce the
same answer.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
