算法分享第5题

题目：Given a string containing just the characters '(',')','{','}','[' and ']', determine if the input string a valid.

the brackets must close in the correct order.

如：'()' and "()[]{}" are all valid but "(]" and "([)]" are not.

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

思路：

• 首先想到的便是使用栈的进出栈来匹配，当发现左括号时进栈，右括号时进行判断;
• 如果栈顶元素为该右括号对应的左括号，则该元素出栈，否则返回不匹配;
• 如果进出栈都无误，则在程序结束后检查栈中是否还有元素，无元素则返回匹配，有元素则返回不匹配.

匹配成功 - ()[]{} 匹配失败 - ([)]

代码：

private boolean match(String str) {
    int length = str.length();
    Stack stack = new Stack();
    for (int index = 0; index < length; index++) {
        char ch = str.charAt(index);
        switch (ch) {
            case '(':
            case '{':
            case '[':
                // 左括号进栈
                stack.push(ch);
                break;
            case ')':
                // 右括号 栈为空 返回false
                if (stack.empty()) {
                    return false;
                // 右括号 栈顶元素不是对应左括号返回false
                } else if ('(' != (char) stack.pop()) {
                    return false;
                }
                break;
            case '}':
                if (stack.empty()) {
                    return false;
                } else if ('{' != (char) stack.pop()) {
                    return false;
                }
                break;
            case ']':
                if (stack.empty()) {
                    return false;
                } else if ('[' != (char) stack.pop()) {
                    return false;
                }
                break;
            default:
                break;
        }
    }
    // 字符串遍历结束后栈为空则代表所有括号匹配成功
    return stack.empty();
}