我在寻找算法后缀到中间符号，这将产生括号中的最小数量。
我发现，但它会产生很多很多括号： 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用括号。 即在算法（见下文）做过的工作。
当你从每个弹出顶部的两个值Stack S，你有3个运营商在眼前：
- 目前运营商
- 在第一个操作数最近使用的运营商（如果运营商存在）
- 在第二个操作数最近使用的运营商（如果运营商存在）
根据这三个运营商，你应该封装与括号中的第一和/或第二个操作数，将它们结合起来了。
您可以使用运算符优先级，以确定是否应该有括号。 顺序是这样的： (none), {"*", "/"}, {"+", "-"}
- 第一个操作数需要括号当且仅当它的操作比目前运营商较低的优先级。
- 第二个操作数需要括号如果操作者具有比当前操作者一个低优先级，或如果它们具有相同的优先级，其中电流运算符为
"/"或"-"。
其余的应该做你的算法所描述的方式。
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)"));
}
文章来源: Postfix to Infix with minimum number of parentheses
