15 Apr 91 08:46:55 GMT

Related articles |
---|

Minimizing parentheses in a postfix->infix converter output acmfiu@fiu.edu (1991-04-13) |

Re: Minimizing parentheses in a postfix->infix converter output ressler@cs.cornell.edu (1991-04-14) |

Re: Minimizing parentheses in a postfix->infix converter output firth@sei.cmu.edu (1991-04-14) |

Re: Minimizing parentheses in a postfix->infix converter output ge@dbf.kun.nl (1991-04-15) |

Newsgroups: | comp.compilers |

From: | ge@dbf.kun.nl (Ge' Weijers) |

Keywords: | design |

Organization: | Compilers Central |

References: | <9104130521.AA00996@fiu.edu> |

Date: | 15 Apr 91 08:46:55 GMT |

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)

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.