Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Postfix to Infix with minimum number of parentheses

I am looking for algorithm postfix to infix notation which will produce the minimum number of the parentheses.

I have found that but it will produce many, many parentheses: http://tajendrasengar.blogspot.com/2011/09/postfix-to-infix-algorithm.html

For example

The input:

<ONP>abcd*/+~

The result:

<INF>~(a+b/(c*d))
like image 552
Yoda Avatar asked Dec 27 '22 06:12

Yoda


1 Answers

What you need to do if you really want as few parentheses as possible, is similar to what the algorithm you linked to says. However...

  • You should store an operator for each composite operand in the Stack. Namely, the last operator used in the operand. You could use a second Stack for this. If the operand is not composite, you could add null to the second Stack, since there is no operator.
  • Don't encapsulate the resulted String with parentheses. That is done elsewhere in the algorithm (see below).

When you pop the top two values from each of the Stacks, you have 3 operators at hand:

  • The current operator
  • The last used operator in the first operand (if the operator exists)
  • The last used operator in the second operand (if the operator exists)

Depending on these three operators, you should encapsulate the first and/or second operand with parentheses, before combining them.

You could use operator precedence to determine whether there should be parentheses. The order goes like this: (none), {"*", "/"}, {"+", "-"}

  • The first operand needs parentheses if and only if its operator has a lower precedence than the current operator.
  • The second operand needs parentheses if its operator has a lower precedence than the current operator, or if they have equal precedence where the current operator is either "/" or "-".

The rest should be done the way your algorithm described.

like image 95
Lone nebula Avatar answered Jan 14 '23 03:01

Lone nebula