使用最少括号括号后缀到中缀

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

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

例如

输入：

abcd*/+~ 

结果：

 ~(a+b/(c*d)) 

Answer 1

如果你真的想要尽可能少的括号，你需要做什么，就像你所链接的算法所说的那样。 然而…

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

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

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

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

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

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

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

Answer 2

这是实施：

 public class PostfixToInfixConverter implements ExpressionConverter { @Override public String convert(String postfix) { String[] expressions = postfix.split("\\s"); Deque stack = new LinkedList(); 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; } } 

}

这是unit testing

 @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("ab + c + 2 *"), equalTo("2*(c+b+a)")); }