Postfix to Infix with minimum number of parentheses

Question

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))

Manouch

Why? What do you care how many parentheses there are? – Mikkel

Answer 1

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.

Diazonium

What about operator precedence? – Palawan

Answer 2

I found an example to solve this problem. There is a _Unparsing class in ast library of python to unparse AST tree.

There is a require_parens function in the library to check parentheses.

Example:

~% python3.11
>>> import ast
>>> ast.unparse(ast.parse("(-(-1+2)+((2*3))-4)"))
'-(-1 + 2) + 2 * 3 - 4'
>>>

If you want you can convert AST tree to postfix notation using a ast.walk function. Link

Myelitis

Answer 3

Here is the implementation:

public class PostfixToInfixConverter implements ExpressionConverter {

@Override
public String convert(String postfix) {
    String[] expressions = postfix.split("\\s");
     Deque<Expression> stack = new LinkedList<Expression>();
    for (String exp : expressions) {
        if (exp.equals("+") || exp.equals("-")) {
            String right = stack.pop().getExpression();
            String left = stack.pop().getExpression();
            Expression newExp = new Expression(right + exp + left, exp);
            stack.push(newExp);
        } else if (exp.equals("*") || exp.equals("/")) {
            String right = correctExpression(stack.pop());
            String left = correctExpression(stack.pop());
            stack.push(new Expression(right +  exp +  left, exp));
        } else {
            stack.push(new Expression(exp, ""));
        }
    }
    return stack.pop().getExpression();
}

private String correctExpression(Expression exp) {
    String result = exp.getExpression();
    if (exp.getOperatorUsed().equals("+") || exp.getOperatorUsed().equals("-")) {
        result = "(" + result + ")";
    }
    return result;
}

private static class Expression {
    String expression;
    String operatorUsed;
    public Expression(String exp, String operator) {
        this.expression = exp;
        this.operatorUsed = operator;
    }
    public String getExpression() {
        return expression;
    }
    public String getOperatorUsed() {
        return operatorUsed;
    }       
}   

}

Here is the unit tests

@Test
public void test() {
    ExpressionConverter converter = new PostfixToInfixConverter();
    assertThat(converter.convert("1 2 * 3 4 * + 5 *"), equalTo("5*(4*3+2*1)"));
    assertThat(converter.convert("a b + c + 2 *"), equalTo("2*(c+b+a)"));
}

Genital

This doesn't minimise parentheses. – Mikkel