減少二進制表達式樹的括號數

Question

我有一個函數接收一個二進制表達式樹，並返回一個字符串與按順序的表達式。唯一的「問題」是由此產生的表達式有太多括號，例如：該函數返回（a +（b * c）），但它可以被簡化爲a + b * c。
它是用二元運算符+， - ，*，/和一元運算符_（負）定義的。
我真正想知道的是，如果我可以修改已有的函數以有效地減少括號的數目，或創建另一個使用按序表達式的字符串操作的函數。
的功能如下：

private static String infijo(ArbolB t){ 
    String s = ""; 
    if (t != null) { 
     String info = String.valueOf(t.info); 
     if ("+-*/".contains(info)) s += "("; 
     if ("_".contains(info)) s += "-("; 
     s += infijo(t.left) + (info.equals("_") ? "" : info) + infijo(t.right); 
     if ("+-*/_".contains(String.valueOf(t.info))) s += ")"; 
    } 
    return s; 
} 

凡ArbolB是定義一個二叉樹：

public class ArbolB { 

    ArbolB right; 
    ArbolB left; 
    Object info; 

    public ArbolB(Object info, ArbolB right, ArbolB left){ 
     this.info = info; 
     this.right = right; 
     this.left = left; 
    } 
} 

Answer 1

滿分作文這件事後，我意識到，我並沒有真正回答你的問題正確（我的解決方案忽略了PEMDAS，只是匹配對，噢！）。所以，從中可以得到什麼......我不會拋出：P

我認爲你可以解決這個問題，但這裏將是我的首選方法，使用和相信你已有的東西。可能有一種很好的方式來使用節點來做到這一點，但爲什麼不使用你所擁有的，對吧？

從點出發，你有你的表達式作爲字符串（如 「（（2 * 2）+ _（3 + 3））」，你可以嘗試這樣的：

public string RemoveUnnecessaryParens(string expression) 
{ 
    readonly string openParen = "("; 
    readonly string closeParen = ")"; 
    // char array would also work for this 
    // multiple ways to track "balance" of parens, lets use int 
    int unclosedParenCount = 0; 

    string toReturn = ""; 

    // iterate through the expression 
    for (int i = 0; i < expression.Length; i++) 
    { 
     string current = expression.Substring(i,1); 
     if (openParen == current) 
      unclosedParenCount++; 
     else if (closedParen == current) 
      unclosedParenCount--; 
     else 
      toReturn += current; 

     if (unclosedParenCount < 0) throw new UnbalancedExpressionException(); // One more close than open! Uh oh! 
    } 

    if (0 != unclosedParenCount) throw new UnbalancedExpressionException(); // One more open than close at the end! Uh oh! 
    else return toReturn; 
} 

有意義嗎？

Answer 2

好吧，經過一段時間的思考，我自己找到了一個解決方案，通過添加確定何時需要括號的優先級函數以及指示操作位於公式的左側還是右側的變量，這是因爲a-b + c不需要括號，但是c +（ab）確實需要它們。

private static String infijo(ArbolB t, int priority, boolean right) { 
    String s = ""; 
    int oP = 0; 
    if (t != null) { 
     String info = String.valueOf(t.info); 
     int pi = priority(info); 
     if ("+-*/".contains(info)) { 
      /* this only adds parentheses if the operation has higher priority or if the 
       operation on the right side should be done before the one on the left side*/ 
      if ("+-*/".contains(info)) { 
       if (pi/2 < priority/2) s += "("; 
       else s += pi/2 == priority/2 && pi != priority && right ? "(" : ""; 
       oP = priority; //stores the old priority 
       priority= pi; //priority of the new operator 
      } 
     } 
     if ("_".contains(info)) { 
      s += "-"; 
      oP = priority; 
      priority = pi; 
     } 
     s += infijo(t.left, priority, false) + (info.equals("_") ? "" : info) 
       + infijo(t.right, priority, true); 
     if ("+-*/".contains(info)) { 
     // adds the closing parentheses following the same rules as for the opening ones 
      if (priority/2 < oP/2) s += ")"; 
      else s += priority/2 == oP/2 && priority != oP && right ? ")" : ""; 
     } 
    } 
    return s; 
} 

private static int priority(String op) { 
    if ("_".contains(op)) return 4; 
    if ("/".contains(op)) return 3; 
    if ("*".contains(op)) return 2; 
    if ("-".contains(op)) return 1; 
          return 0; 
} 

@Override 
public String toString() { 
    ArbolB f = getFormula(); //this returns the Binary Expression Tree 
    return infijo(f, Integer.MIN_VALUE, false); 
}