Stack，圓括號匹配

Question

所以我正在用PostFix和Infix表達式做一些作業。我遇到了一些問題，似乎無法找到我遇到問題的位置。大部分我都可以通過Postfix工作。當我不希望它被打印時，我得到一些（或）打印的等式。另外，當我沒有匹配的括號時，我不會收到像我想要的那樣的錯誤。

public String Infix(String equation) throws Exception{ 
    Stack stack=new Stack(); 
    boolean parensMatch=false; 
    int priority=0; 
    String temp=""; 
    for(int i=0; i<equation.length(); i++){ 
     char c=equation.charAt(i); 
     //if the character is equal to left paren, push 
     if(c=='('){ 
      stack.push(c); 
     } 
     //if the character is equal to right paren, we start popping until we find a match 
     else if(c==')'){ 
      try{ 
       while(stack.peek()!='('){ 
        temp+=stack.pop(); 
       } 

       if(stack.peek()=='('){ 
        char ch=stack.pop(); 
        parensMatch=true; 
       } 

       if(parensMatch==false){ 
        throw new Exception("Parens Not Match Error"); 
       } 
      }catch(Exception e){ 
       System.out.println(e); 
      } 
      parensMatch=false; 
     } 
     //if the character is equal to an operator, we do some extra work 
     //to figure out what is going to happen 
     else if(c=='+' || c=='-' || c=='*' || c=='/' || c=='^'){ 
      char top=stack.peek(); 
      if(top=='^') 
       priority=2; 
      else if(top=='*' || top=='/') 
       priority=1; 
      else 
       priority=0; 
      if(priority==2){ 
       if(c=='*' || c=='/'){ 
        temp+=stack.pop(); 
       } 
       else if(c=='+' || c=='-'){ 
        temp+=stack.pop(); 
       } 
       else{ 
        temp+=stack.pop(); 
       } 
      } 
      else{ 
       if(c=='*' || c=='/'){ 
        temp+=stack.pop(); 
        stack.push(c); 
       } 
       else if(c=='+' || c=='-'){ 
        stack.push(c); 
       } 
       else{ 
        stack.push(c); 
       } 
      } 
     } 
     //if the character is a space, we ignore it and move on 
     else if(c==' '){ 
      ; 
     } 
     //if the character is a letter, we add it to the string 
     else{ 
      temp+=c; 
     } 
    } 
    int len = stack.size(); 
    for (int j = 0; j < len; j++) 
     temp+=stack.pop(); 
    return temp; 
} 

這是我對綴後綴方法

(((A + B) - (C - D))/(E - F))這是我需要解決的表情之一，AB+CD--(EF-/是我所得到的，當它打印到屏幕上。 ((A是另一個，這個應該給我一個錯誤，但A((被打印到屏幕上。

我一直在運行調試很長一段時間，似乎無法獲得任何地方。

任何幫助將是非常有幫助的。我知道它與發佈的代碼有關，但我無法找到邏輯錯誤。提前致謝！

所以我添加了一個新的功能來幫助匹配parens，我認爲它會很有用。它採用方程式並只計算它們是否匹配。

public static int matchingParens(String equation){ 
    int match=0; 

    for(int i=0; i<equation.length(); i++){ 
     char c=equation.charAt(i); 
     if(c=='(') 
      match++; 
     else if(c==')') 
      match--; 
     else 
      ; 
    } 

    return match; 
} 

Answer 1

爲了驗證是否括號都匹配了，你可以通過與0初始值的計數器的數學表達式你的字符串輸入運行，如果你找到一個(，加1的計數器，如果你發現)，則將你的計數器減1。如果計數器達到-1，則發生，因爲它不是有效的括號匹配。最後，您應該將計數器的值設爲0.如果不是，則會有不匹配的括號。

對於綴以後綴的情況下，這裏有一個標準的算法：

Define a stack 
Go through each character in the string 
If it is between 0 to 9, append it to output string. 
If it is left brace push to stack 
If it is operator *,+,- or/then 
      If the stack is empty push it to the stack 
      If the stack is not empty then start a loop: 
          If the top of the stack has higher precedence 
          Then pop and append to output string 
          Else break 
        Push to the stack 

If it is right brace then 
      While stack not empty and top not equal to left brace 
      Pop from stack and append to output string 
      Finally pop out the left brace. 

Answer 2

嗯，我想給你一些「軟件工程」提示，這到底能解決你的問題，你可以學到很多東西通過做「很好」。

數學表達式，無論你是按照pre，in，post的順序編寫它們，看起來總是一樣的，如果你將它們存儲在某個樹結構中的話。然後，如果要將該樹結構打印到字符串中，則只需遍歷整個樹，並且只在當前時刻（以及某些情況下的其他大括號）變化時纔會寫入該字符串。

預訂當您第一次進入該節點時執行此操作，當您完成左側子節點和Postorder時，請執行此操作，如果您在離開節點時執行此操作。

我的建議是：

類：Expression，UnaryExpression extends Expression，BinaryExpression extedns Expression然後你就可以讓數字和運算符：Add extends BinaryExpression等。

那麼你應該有一流的Tree，它存儲了Expression root，它有方法printPreOrder()，printInOrder()，printPostOrder()

要創建樹，這將是非常不錯的使用可以這樣使用的Builder pattern：

public class Director { 
    private IExpressionBuilder builder; 

    public ArithmeticExpression construct(String text){ 
       for (int i=0;i<text.length();i++){ 
        if (text.charAt(i) == '+'){ 
         builder.buildAddOperator(); 
        } 
        ... 
       } 
    } 

，然後創建具體的生成器類，如下所示：

public class InOrderBuilder implements IExpressionBuilder { 

    public void buildAddOperator() { 
     ... 
    } 
    .... 
}