用最少數量的括號將後綴添加到中綴

Question

我正在尋找算法後綴來插入符號，這會產生最小數量的括號。

我發現，但它會產生很多很多括號：http://tajendrasengar.blogspot.com/2011/09/postfix-to-infix-algorithm.html

例如

輸入：

<ONP>abcd*/+~ 

結果：

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

Answer 1

如果你需要做什麼ou確實希望儘可能少括號，與您所鏈接的算法相似。然而...

• ，可以儲存運營商在Stack每個複合操作。即操作數中使用的最後一個運算符。你可以爲此使用第二個Stack。如果操作數不是合成的，則可以將null添加到第二個Stack，因爲沒有操作員。
• 請勿用括號封裝生成的String。這在算法的其他地方完成（見下文）。

當你從每個Stack S的彈出頂部的兩個值，你有3個運營商在眼前：

• 目前運營
• 在第一個操作數最近使用的運營商（如果操作者存在）
• 最後使用的操作員在第二操作數（如果操作者存在）

根據這些第ree操作符，在組合它們之前，應該用圓括號封裝第一個和/或第二個操作數。

您可以使用運算符優先級來確定是否應該有括號。順序如下：(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)")); 
}