題目:

給定一個只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判斷字符串是否有效。

有效字符串需滿足：

左括號必須用相同類型的右括號閉合。
左括號必須以正確的順序閉合。
注意空字符串可被認為是有效字符串。

解題思路:

想象一下，你正在為你的大學課設編寫一個小型編譯器，編譯器的任務之一（或稱子任務）將檢測括號是否匹配。

我們本文中看到的算法可用于處理編譯器正在編譯的程序中的所有括號，并檢查是否所有括號都已配對。這將檢查給定的括號字符串是否有效，是一個重要的編程問題。

我們這個問題中將要處理的表達式可以包含以下三種不同類型的括號：

()，
{} 以及
[]
在查看如何檢查由這些括號組成的給定表達式是否有效之前，讓我們看一下該問題的簡化版本，在簡化后的問題中，只含一種類型的括號。這么一來，我們將會遇到的表達式是

(((((()))))) – VALID

()()()() – VALID

(((((((() – INVALID

((()(()))) – VALID
上我們試著用一個簡單的算法來解決這一問題。

我們從表達式的左側開始，每次只處理一個括號。
假設我們遇到一個開括號（即 (），表達式是否無效取決于在該表達式的其余部分的某處是否有相匹配的閉括號（即 )）。此時，我們只是增加計數器的值保持跟蹤現在為止開括號的數目。left += 1
如果我們遇到一個閉括號，這可能意味著這樣兩種情況：
此閉括號沒有與與之對應的開括號，在這種情況下，我們的表達式無效。當 left == 0，也就是沒有未配對的左括號可用時就是這種情況。
我們有一些未配對的開括號可以與該閉括號配對。當 left > 0，也就是有未配對的左括號可用時就是這種情況。
如果我們在 left == 0 時遇到一個閉括號（例如 )），那么當前的表達式無效。否則，我們會減少 left 的值，也就是減少了可用的未配對的左括號的數量。
繼續處理字符串，直到處理完所有括號。
如果最后我們仍然有未配對的左括號，這意味著表達式無效。

如果我們只是嘗試對原始問題采用相同的辦法，這是根本就行不通的?；诤唵斡嫈灯鞯姆椒軌蛟谏厦嫱昝肋\行是因為所有括號都具有相同的類型。因此，當我們遇到一個閉括號時，我們只需要假設有一個對應匹配的開括號是可用的，即假設 left > 0。

但是，在我們的問題中，如果我們遇到 ]，我們真的不知道是否有相應的 [ 可用。你可能會問：

為什么不為不同類型的括號分別維護一個單獨的計數器？

這可能不起作用，因為括號的相對位置在這里也很重要。例如：

[{]
如果我們只是在這里維持計數器，那么只要我們遇到閉合方括號，我們就會知道此處有一個可用的未配對的開口方括號。但是，最近的未配對的開括號是一個花括號，而不是一個方括號，因此計數方法在這里被打破了。

方法：棧

此外，如果仔細查看上述結構，顏色標識的單元格將標記開閉的括號對。整個表達式是有效的，而它的子表達式本身也是有效的。這為問題提供了一種遞歸結構。例如，考慮上圖中兩個綠色括號內的表達式。開括號位于索引 1，相應閉括號位于索引 6。

如果每當我們在表達式中遇到一對匹配的括號時，我們只是從表達式中刪除它，會發生什么？

在表示問題的遞歸結構時，棧數據結構可以派上用場。我們無法真正地從內到外處理這個問題，因為我們對整體結構一無所知。但是，?？梢詭椭覀冞f歸地處理這種情況，即從外部到內部。

讓我們看看使用棧作為該問題的中間數據結構的算法。

算法

初始化棧 S。
一次處理表達式的每個括號。
如果遇到開括號，我們只需將其推到棧上即可。這意味著我們將稍后處理它，讓我們簡單地轉到前面的 子表達式。
如果我們遇到一個閉括號，那么我們檢查棧頂的元素。如果棧頂的元素是一個 相同類型的 左括號，那么我們將它從棧中彈出并繼續處理。否則，這意味著表達式無效。
如果到最后我們剩下的棧中仍然有元素，那么這意味著表達式無效。
我們來看一下該算法的動畫演示，然后轉到實現部分。

代碼實例:

public class program2test {// Hash table that takes care of the mappings.private HashMap<Character, Character> mappings;// Initialize hash map with mappings. This simply makes the code easier to// read.public program2test() {this.mappings = new HashMap<Character, Character>();this.mappings.put(')', '(');this.mappings.put('}', '{');this.mappings.put(']', '[');}public boolean isValid(String s) {// Initialize a stack to be used in the algorithm.Stack<Character> stack = new Stack<Character>();for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);// If the current character is a closing bracket.if (this.mappings.containsKey(c)) {// Get the top element of the stack. If the stack is empty, set// a dummy value of '#'char topElement = stack.empty() ? '#' : stack.pop();// If the mapping for this bracket doesn't match the stack's top// element, return false.//this.mappings.get(c)是獲取c鍵的值if (topElement != this.mappings.get(c)) {return false;}} else {// If it was an opening bracket, push to the stack.stack.push(c);}}// If the stack still contains elements, then it is an invalid// expression.return stack.isEmpty();}public static void main(String[] args) {program2test n = new program2test();String s = "{{{}}}";System.out.println(n.isValid(s));} }

總結

以上是生活随笔為你收集整理的java有效的括号的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。