Re: Minimizing parentheses in a postfix->infix converter output

In comp.compilers acmfiu@fiu.edu writes:


>I have a postfix->infix converter and need to output the least number of
>parentheses as possible. The resulting infix expression is kept in a
>binary tree and I just traverse the tree outputting the left/right
>parentheses at each level. ...


I assume you use a recursive traversal routine on the tree. The algorithm
is not hard. Just pass a priority to this expression-printer:


prio[ADD] := 1;
prio[MUL] := 2;


PROCEDURE PrintExpression (node: EXPRESSION, ctxPrio: PRIO);
BEGIN
IF node is primary
THEN PrintPrimary(node);
ELSIF node is binary operator expression
THEN
IF ctxPrio > prio[node^.operator]
THEN write('(');
END;
PrintExpression(node^.left, prio[node^.operator]+1);
write(repr[node^.operator]);
PrintExpression(node^.right, prio[node^.operator]);
IF ctxPrio > prio[node^.operator]
THEN write(')');
END
ELSE
... (* other syntactic constructs *)
END
END PrintExpression;


This works for languages that have left-to-right binding. The algorithm can
be made more general by adding left- and right-priority arrays, for instance
for right-to-left binding X ** Y operators.


As you can see deciding whether to print the parentheses requires knowledge
of the operator one level up in the tree. In RPN this operator can
be arbitrarily far ahead in the input.
I'm afraid you have to use a tree or reading the expression backwards.
This gives an unreversed Polish or prefix representation of the tree,
which can be scanned by an algorithm quite similar to the tree traversal
algorithm.


--
Ge' Weijers Internet/UUCP: ge@cs.kun.nl
Faculty of Mathematics and Computer Science, (uunet.uu.net!cs.kun.nl!ge)
University of Nijmegen, Toernooiveld 1
6525 ED Nijmegen, the Netherlands tel. +3180652483 (UTC-2)
--

Return to the comp.compilers page.
Search the comp.compilers archives again.