Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!swrinde!cs.utexas.edu!sun-barr!olivea!mintaka!spdcc!iecc!compilers-sender
From: ge@dbf.kun.nl (Ge' Weijers)
Newsgroups: comp.compilers
Subject: Re: Minimizing parentheses in a postfix->infix converter output
Keywords: design
Message-ID: <2953@wn1.sci.kun.nl>
Date: 15 Apr 91 08:46:55 GMT
References: <9104130521.AA00996@fiu.edu>
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: ge@dbf.kun.nl (Ge' Weijers)
Organization: Compilers Central
Lines: 53
Approved: compilers@iecc.cambridge.ma.us

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)
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.