括号配对问题
括号配对问题
http://www.nowcoder.com/questionTerminal/57260c08eaa44feababd05b328b897d7
题目难度：二星
考察点：栈
方法：字符串
1.分析：
这是一个经典的括号匹配问题，只不过需要入栈的元素由一个变成了两个，而且这个题的题意不是很明确，如果包含除了括号之外的字符也是可以的。我们可以采用如下的步骤进行判断：
0. 首先定义一个栈st，栈所包含的元素为字符。
1. 遍历输入的括号序列，如果是'('或者是'['，那么就进栈，即st.push(s[i]);
2. 如果当前遍历到')'，那么首先判断栈是否为空，如果栈为空，那么匹配失败，否则判断栈顶元素是否为'('，如果当前栈顶元素不为'('，则匹配失败
2. 如果当前遍历到')'，那么首先判断栈是否为空，如果栈为空，那么匹配失败，否则判断栈顶元素是否为'('，如果当前栈顶元素不为'('，则匹配失败
3. 如果当前遍历到']'，那么还是先判断栈是否为空，如果栈为空，那么匹配失败，否则判断栈顶元素是否为'['，如果当前栈顶元素不为'['，则匹配失败
4. 如果当前为其它字符，不进行操作
5. 若能顺利遍历完成，那么需要检查栈中是否还有剩余元素，如果有，则匹配失败；如果没有，则匹配成功。
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(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;
}
查看4道真题和解析
