二. 栈 1 有效的括号序列

问题：给定一个字符串所表示的括号序列，包含以下字符： '(', ')', '{', '}', '[' and ']'，判定是否是有效的括号序列
如括号必须依照 "()" 顺序表示， "()[]{}" 是有效的括号，但 "([)]"则是无效的括号。

思路：括号最重要的是匹配，只要出现()[]{}，就可以抵消掉，否则就false，而且对于stack的第一个元素不能是}])，其他的就可以push入栈。
这里，我们用数组来模拟stack，string作为输入源。
注意匹配的顺序，不能是“)(”。
Python3

class Solution:
    # @param {string} s A string
    # @return {boolean} whether the string is a valid parentheses
    def isValidParentheses(self, s):
        # Write your code here
        stack = []
        for index in s:
            if index == "(" or index == "{" or index == "[":
                stack.append(index)
                continue
            length = len(stack)
            if stack:
                if index == ")" and  stack[length - 1] == "(":
                    stack.pop()
                    continue
                if index == "}" and  stack[length - 1] == "{":
                    stack.pop()
                    continue
                if index == "]" and  stack[length - 1] == "[":
                    stack.pop()
                    continue
                else:
                    return False
            else:
                if index == "}" or index == "]" or index == ")":
                    return False

        if stack:
            return False
        else:
            return True

这里，我有遇到一个问题，如何判断一个数组为空。
stack == None 是行不通的。
亲测以下均可：

a = []
if not bool(a):

if not a:

if len(a) == 0:

if a == []:

也就是说，一个空的列表 == 0 == False

java

public class Solution {
    /**
     * @param s A string
     * @return whether the string is a valid parentheses
     */
    public boolean isValidParentheses(String s) {
        // Write your code here
        Stack<Character> stack = new Stack<Character>();
        for (char bracket: s.toCharArray())
        {
            if (bracket == '(')
            {
                stack.push(')');
            }
            else if (bracket == '{')
            {
                stack.push('}');
            }
            else if (bracket == '[')
            {
                stack.push (']');
            }
            else if (stack.isEmpty() || bracket != stack.pop())
            {
                return false;
            }
        }
        return stack.isEmpty();
    }
}

在用java做的时候，我发现了一个好方法，就是如上思路，简洁可行。

也发现了几个问题：

java中 “{” 和 ‘{’ 是不一样的类型：第一个是string 第二个是 char。
java中有现成的stack，c++也有，反而就是python没有。但是他们建立顺序栈的方式都差不多，均用了数组。

下面就是相关的信息：
Java 数据结构包括：枚举（Enumeration）位集合（BitSet）向量（Vector）栈（Stack）字典（Dictionary）哈希表（Hashtable）属性（Properties）

Python3数据结构包括：列表（栈，队列）集合，字典，元组

二. 栈 1 有效的括号序列

推荐阅读更多精彩内容