java - 带有最少括号数的中缀后缀

Question

我正在寻找算法后缀来中缀符号，这将产生最小数量的括号。

我发现了，但它会产生很多很多括号：http ://tajendrasengar.blogspot.com/2011/09/postfix-to-infix-algorithm.html

例如

输入：

<ONP>abcd*/+~

结果：

<INF>~(a+b/(c*d))

Answer 1

如果你真的想要尽可能少的括号，你需要做什么，类似于你链接到的算法所说的。然而...

• 您应该将每个复合操作数的运算符存储在Stack. 即，操作数中使用的最后一个运算符。您可以为此使用一秒钟Stack。如果操作数不是复合的，则可以添加null到第二个Stack，因为没有运算符。
• 不要String用括号封装结果。这是在算法的其他地方完成的（见下文）。

当您从每个Stacks 中弹出前两个值时，您手头有 3 个运算符：

• 当前运营商
• 第一个操作数中最后使用的运算符（如果该运算符存在）
• 第二个操作数中最后使用的运算符（如果该运算符存在）

根据这三个运算符，您应该在组合它们之前用括号封装第一个和/或第二个操作数。

您可以使用运算符优先级来确定是否应该有括号。顺序是这样的：(none), {"*", "/"}, {"+", "-"}

• 当且仅当其运算符的优先级低于当前运算符时，第一个操作数才需要括号。
• 如果第二个操作数的运算符的优先级低于当前运算符，或者在当前运算符为 or 的情况下它们具有相同的优先级，则第二个操作数需要"/"括号"-"。

其余的应该按照您的算法描述的方式完成。

Answer 2

这是实现：

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;
    }       
}   

}

这是单元测试

@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)"));
}