[Java]LeetCode-Valid Parentheses

Posted on by Mingray



這題為表示合法化括號

題目

  1. Valid Parentheses
    難度:Easy

Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.

Example 1:
Input: “()”
Output: true

Example 2:
Input: “()[]{}”
Output: true

Example 3:
Input: “(]”
Output: false

Example 4:

Input: “([)]”
Output: false

Example 5:
Input: “{[]}”
Output: true

class Solution {
    public boolean isValid(String s) {

        if(s.equals("")||s==null) \\空的回傳合法
            return true;

        Stack<Character> stack = new Stack<Character>(); \\建立一個stack

        \\stack規則:後進先出

        if (s.length() % 2 != 0)
            return false; \\如果不是雙數，必不合法

        char[] ca = s.toCharArray(); 

        if ( ca[0] == ')' || ca[0] == ']' || ca[0] == '}')
            return false; \\如果第一個非左括號，必錯

        try{
                for (int i = 0; i < ca.length; i++) {

                char temp = ca[i];
                \\遇到右括號，先pop出已存進stack的資料，若不相符則回傳錯誤
                if (temp == ')') {
                    char sc = stack.pop();
                    if (sc != '(')
                        return false;
                } else if (temp == ']') {
                    char sc = stack.pop();
                    if (sc != '[')
                        return false;
                } else if (temp == '}') {
                    char sc = stack.pop();
                    if (sc != '{')
                        return false;

                } else { \\非右括號的全都存進stack
                    stack.push(ca[i]);
                }
            }
        }
        catch(Exception e){ //若stack.pop不出來，會挑出例外，代表不成對回傳錯誤
            return false;
        }
        if(!stack.empty()) //如果已經結束了，stack還沒空代表錯誤
            return false;

        return true;

    }
}

發表迴響