確保括號是平衡的？

Question

我負責創建檢查，如果一些小「（」和大「[」括號和正確關閉的功能。例如...

(()) [] ([])[(())] 

...是正確的，但.. 。

() [(]) 

...不正確。

如何開始處理這個問題有什麼建議？使用遞歸函數被禁止。

---

這是我到目前爲止有：

{ 
    int nr_ap_x = 0; // fie x - "(" 
    int nr_ap_y = 0; // fie y - ")" 
    boolean corect = true; 

    for (int i=0; i < sir.length; i++) 
    { 
     if (sir[i].compareTo("(") == 0) nr_ap_x++; 
     else 
      if (sir[i].compareTo(")") == 0) nr_ap_y++; 
     if (nr_ap_x < nr_ap_y) corect = false; 
    } 
    if (nr_ap_x != nr_ap_y) corect = false; 
    if (corect) System.out.println("Parantezele sunt inchise corect ! "); 
    else System.out.println("Parantezele NU sunt inchise corect ! "); 
} 

Answer 1

提示：保持一個數據結構包含打開字形，並使用和更新時關閉標誌符號出現。

Answer 2

任何用遞歸完成的事情也可以通過迭代完成。如果您已經知道如何遞歸執行，則將其映射到while循環。這在Replace Recursion with Iteration中有解釋。

Answer 3

你可以使用一個確定性有限自動機 - http://en.wikipedia.org/wiki/Deterministic_finite-state_machine

Answer 4

如何做到這一點的總體概況（假設你有一個包含中括號內的字符串數組）：

• 創建堆棧，它包含字符串。
• 對於每個「（」或「[」，推入堆棧
• 對於每個「）」或「]」，檢查堆棧的頂端是否與括號的類型匹配。
  • 如果存在，則丟棄堆棧頂部。
  • 否則，括號不匹配。

如果你有一個非空棧，一旦您的所有字符串用完了，你也有不匹配的括號。