leetcode中和括号匹配相关的问题共有三个，分别是：
Valid Parentheses
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
该提比较简单，正常情况下直接用堆栈就可以了，但有一次面试要求必须要用递归写，其实也很简单，具体参考这里
Longest Valid Parentheses
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.
该题目使用动态规划来计算，dp[i]表示到第i个位置的最大长度，由于匹配的括号必须是连续的，所以，如果有j < i 且j和i匹配，则dp[i] = (i-j+)+dp[j]。
从转移方程来看，好像是二维DP，但是可以使用堆栈来转化为一维的，简单来说，就是遇到左括号就进栈，遇到右括号就出栈，而出栈的位置就是上
面的j，所以不需要进行二维扫描就可定位到j。
class Solution {
public:
int longestValidParentheses(string s) {
int length = s.size(),i,maxLength = 0;
vector
dp(length,0);
stack
stk; // 左括号的下标 for(i = 0; i < length;++i) { if(s[i] == '(')stk.push(i); else { if(!stk.empty()) { int start = stk.top(); stk.pop(); dp[i] = i - start + 1; if(start > 0)dp[i] += dp[start-1]; if(dp[i] > maxLength)maxLength = dp[i]; } } } return maxLength; } };
Generate Parentheses
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"
该问题是著名的卡特兰数，具体参考该博客