20. Valid Parentheses

今天要挑战是第二十题合法括号，这题也是非常经典而且有趣的，其中还会使用「堆叠」(Stack)这样子的资料结构，能帮助完成题目要求，接下来就让我们一起来看看这一题吧！

题目

Given a string s 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.

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Example 4:

Input: s = "([)]"
Output: false

Example 5:

Input: s = "{[]}"
Output: true

这一题顾名思义就是要我们检查一串括号是否为合法括号，而合法括号的要件是要左括号等於右括号的数量，并且要两两成对，且相同类型的括号要配相同类型的括号（譬如大括号要配大括号）。如果是合法括号就回传true，否则回传false。

堆叠 Stack

堆叠是一种储存资料的方式，其最大的特色就是具有後进先出（LastInFirstOut=>LIFO）的特性，在这一题括号合法的问题上，正好可以利用这样的特性解，原因是括号的逻辑与之正好相符，一个合法括号，由於是两两相对，第一个是对到最後一个，第二个对到倒数第二个，因此永LIFO的原则，正好可以让第一个与最後一个做比对，形成两两比对的规则，以下会跟清楚讲解在此题的应用方式。

堆叠解法

此解法会先建立一个堆叠，假如括号为左括号就先加入堆叠，如果是右括号则比对与堆叠最上层的括号是否成对，如果是的话就把最上层的括号丢掉（用pop），最後再检查堆叠中是否还有括号，如果没有就表示这是一个合法的括号，如果有则非合法括号。
在python中我们可以透过对list的操作，包括list[-1]、list.append()与list.pop()的方式模拟一个堆叠的资料型态，因为这些操作的时间复杂度都是big O(1)的，因此不会过於浪费时间。而在C++中可以使用stack内建的资料型态进行相对应的函数处理，以下展示两种不同语言的程序码。

以下是python的程序码

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for i in s:
            if not stack:
                stack.append(i)
            elif (i == ")" and stack[-1] == "(") or \
                (i == "]" and stack[-1] == "[") or \
                    (i == "}" and stack[-1] == "{"):
                stack.pop()
            else:
                stack.append(i)

        if not stack:
            return True
        else:
            return False

以下是C++的程序码

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;  //创建堆叠
        for(char i: s){
            if (st.empty() || i == '(' || i == '[' || i == '{'){
                st.push(i);  //如果是左括号或堆叠为空，就加入堆叠
            }
            else if (i == ')' && st.top() == '(' || i == ']' && st.top() == '[' || 
                    i == '}' && st.top() == '{'){
                st.pop();  //如果是右括号，比对相符就把堆叠最上层丢掉
            }
            else{
                return false; //如果皆非上述情形，表示括号非法，回传flase
            }   
        }
        return st.empty();  //最後如果堆叠为空就回传true
    }
};

参考资料