| I'm having a bit of a problem. I've created a parse tree in memory
| like the following.
|
|
| *
| / \
| ! c
| \
| +
| / \
| a b
|
| When I traverse the tree in a inorder traversal I get !a+b*c,
| which is correct. The problem is I have to restore the parentheses
| so that I get !(a+b)*c. How can I do this when I and doing
| the traversal recursively. For example, [ deleted ... ]
Define a precedence relation for all the binary and monary
operators, as well as the operands (constants and identifiers):
something like:
prec oper
----+----
5 |NULL
4 |const, ident
3 |!
2 |*, /
1 |+, -
The (recursive) inorder traversal looks something like this:
void in_trav(node_t* t, int par) {
if (t) {
if (par) putchar('(');
in_trav(t->left, prec(t->left, t));
printf("%c", t->oper);
in_trac(t->right, prec(t->right, t));
if (par) putchar(')');
}
}
The function prec(x, y) returns a non-zero value iff
prec(x->oper) < prec(y->oper) (including the special case where
x or y equals NULL, in which case prec() returns any value.)
The top level call of in_trav() passes a zero value as the
second argument, i.e. the entire expression need not be
parenthesized ...
kind regards,
----------------------------------------------------------------------------
Two things are omnipresent in the universe: hydrogen and my stupidity
Parse trees and "("")"