Postfix to Infix with minimum number of parentheses
infix-notation, java, postfix-notation
Solution
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 `Stack`s, 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.
Problem
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)) ```