题目难度：二星
考察点：栈

方法：字符串

1.分析：

这是一个经典的括号匹配问题，只不过需要入栈的元素由一个变成了两个，而且这个题的题意不是很明确，如果包含除了括号之外的字符也是可以的。我们可以采用如下的步骤进行判断：
0. 首先定义一个栈st，栈所包含的元素为字符。
1. 遍历输入的括号序列，如果是'('或者是'['，那么就进栈，即st.push(s[i]);
2. 如果当前遍历到')'，那么首先判断栈是否为空，如果栈为空，那么匹配失败，否则判断栈顶元素是否为'('，如果当前栈顶元素不为'('，则匹配失败
3. 如果当前遍历到']'，那么还是先判断栈是否为空，如果栈为空，那么匹配失败，否则判断栈顶元素是否为'['，如果当前栈顶元素不为'['，则匹配失败
4. 如果当前为其它字符，不进行操作
5. 若能顺利遍历完成，那么需要检查栈中是否还有剩余元素，如果有，则匹配失败；如果没有，则匹配成功。
举个例子：假设有一个字符串s = "ab[()]cd"：
那么用指针i表示字符串遍历的下标, st表示栈中元素
当i=0时，s[i]='a'，此时什么也不进行操作
当i=1时，s[i]='b'，此时什么也不进行操作
当i=2时，s[i]='['，此时要将[进栈，即栈中现在有'['
当i=3时，s[i]=']'，此时栈顶元素为'['，正好能够匹配，那么测试弹栈，所以栈为空
当i=4时，s[i]='(，此时要将(进栈，即栈中现在有'('
当i=5时，s[i]=')'，此时栈顶元素为')'，正好能够匹配，那么测试弹栈，所以栈为空
当i=6时，s[i]='c'，此时什么也不进行操作
当i=7时，s[i]='d'，此时什么也不进行操作
遍历结束，此时栈为空，所以S字符串匹配成功。

2.复杂度分析：


时间复杂度：O(n) 
空间复杂度：O(1)

3.代码：  

#include <bits/stdc++.h>
using namespace std;
bool check(string s) {
    int len = s.size();
    stack<char> st;
    for(int i=0; i<len; i++) {
        if(s[i]=='(' || s[i] == '[') st.push(s[i]);
        else if(s[i] == ')') {
            if(st.empty() || st.top()!='(') return 0;
            st.pop();
        }
        else if(s[i] == ']') {
            if(st.empty() || st.top()!='[') return 0;
            st.pop();
        }
    }
    return st.empty();
}
int main(){
    string s; cin>>s;
    stack<char> st;
    if(check(s)) cout<<"true"<<endl;
    else cout<<"false"<<endl;
    return 0;
}