20. Valid Parentheses

题意：

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.

思路：

也是最基本的数据结构的题。。我简直怀疑我们考研题都是从leetcode简单题里找的了。。。
用一个栈，前括号放进去，后括号就取栈顶元素（若栈为空直接false），若不对应返回false。最后若返回st.empty()，栈为空表示每个括号都一一对应，不为空说明有前括号并没有对应的后括号。

bool isMatch(char &a, char &b) {
	switch (a){
	case '(':return b == ')';
	case '[':return b == ']';
	case '{':return b == '}';
	}
	return false;
}

bool isValid(string s) {
	stack<char> st;
	int sz = s.size();
	char temp;
	for (int i = 0; i < sz; ++i) {
		temp = s[i];
		if (temp == '(' || temp == '[' || temp == '{')
			st.push(temp);
        else if(st.empty())
            return false;
		else if (isMatch(st.top(), temp))
			st.pop();
		else
			return false;
	}
	return st.empty();
}