1.简单括号的匹配

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.

用数据结构栈即可完成算法

class Solution {public:    bool isValid(string s) {       stack
    
      paren;        for (char& c : s) {            switch (c) {            case '(':            case '{':            case '[': paren.push(c); break;            case ')': if (paren.empty() || paren.top() != '(') return false; else paren.pop(); break;            case '}': if (paren.empty() || paren.top() != '{') return false; else paren.pop(); break;            case ']': if (paren.empty() || paren.top() != '[') return false; else paren.pop(); break;            default:; // pass            }        }        return paren.empty();    }};
    

2.产生括号匹配

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:

[

"((()))",

"(()())",

"(())()",

"()(())",

"()()()"]

产生括号经典的方法就是回溯

class Solution {public:    void backtrack(vector
    
     &res,string s,int open,int close,int n)    {        if(s.size()==2*n)        {            res.push_back(s);            return;        }        if(open
     
       generateParenthesis(int n) {        vector
      
       res;        backtrack(res,"",n,0);        return res;    }};
      
     
    

3.最长括号匹配

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.

这个方法即是把匹配不上的两个括号储存在stack中，最后再比较两个的大小

注意从-1的位置到第一个未匹配的括号还是要比较的，所以就有了 res=max(res,b); 这一句

class Solution {public:    int longestValidParentheses(string s) {        stack
    
     m;        for(int i = 0;i
     
      b-a-1?res:b-a-1;    }};