[LeetCode] Valid Parentheses 驗證括号是否有效閉合

連結： https://leetcode.com/problems/valid-parentheses/#/description

難度：Easy

題目：20. Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

翻譯：給定一個僅包含字元'（'，'）'，'{'，'}'，'['和']'的字元串，确定輸入字元串是否有效。括号必須以正确的順序關閉，“（）”和“（）[] {}”都是有效的，但“（]”和“（[）]”不是。

思路：用資料結構——棧就可以實作。周遊字元串，把左括号壓棧，碰到右括号就把棧的頂部元素拿出來與右括号比對，比對成功則頂部元素出棧，進入下一次循環，比對不成功或者棧中無元素，則字元串不是有效閉合。直到所有元素周遊完，棧中無元素，即為有效閉合；如果所有元素周遊完了，棧中還有元素，則不是有效閉合。

基礎概念

在 Java 中 Stack 類表示後進先出（LIFO）的對象堆棧。棧是一種非常常見的資料結構，它采用典型的先進後出的操作方式完成的。每一個棧都包含一個棧頂，每次出棧是将棧頂的資料取出，如下：

Stack 通過五個操作對 Vector 進行擴充，允許将向量視為堆棧。這個五個操作如下：

示例代碼:

//Create the Stack instance and add a couple of elements to it
Stack stack = new Stack();
String s1 = "element 1";
String s2 = "element 2";
stack.push(s1);
stack.push(s2);
System.out.println(stack.peek());
//element 2
//Find position of a certain element
int pos = stack.search("element 1");
System.out.println(pos);
//2
System.out.println(stack.pop());
System.out.println(stack.pop());
//element 2
//element 1
System.out.println(stack.empty());
//true
           

參考代碼：

Java

public class Solution {
    public boolean isValid(String s) {
        if(s==null || s.length()==0)
            return false;
        Stack<Character> parentheses = new Stack<Character>(); 
        for (int i = 0; i< s.length(); i++){
            char c = s.charAt(i); 
            if(c=='(' || c=='[' || c =='{')
                parentheses.push(c);
            else{
                if (parentheses.empty())
                    return false;
                if (c == ')' && parentheses.peek() != '(')
                    return false;
                if (c == ']' && parentheses.peek() !='[')
                    return false;
                if (c == '}' && parentheses.peek() !='{')
                    return false;
                parentheses.pop();
            }
        }
        return parentheses.empty();
    }
}
           

參考資料

http://outofmemory.cn/code-snippet/2087/java-usage-Stack-class