括号匹配

对括号匹配有着特别的感情。在一年多前,初学C++时,就遇见过此题。

思想: 左括号进栈,右括号出栈。


代码中用到了C++,STL中的stack。当然也可以自己封装。

简要介绍下stack中的各个方法

s.push(x)

无返回值,将元素x压栈

s.pop()

退栈,无返回值

s.top()

取栈顶元素,返回栈顶元素

s.empty()

判断栈是否为空,如果是空,返回1,否则返回0

s.size()

返回栈中元素的个数


实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <stack>
using namespace std;

int main(int argc, char *argv[])
{
stack<char> s;
char a[101];
gets(a);
int flag=0,i,len =strlen(a); // 若flag为1,则不匹配
for(i=0;i < len; i++){

switch(a[i]){
case '(':
case '[':
case '{': s.push(a[i]); break;
case ')':{
if(s.top() != '('){
flag = 1;

} else{
s.pop();
}
}
break;
case ']':{
if(s.top() != '['){
flag = 1;

} else{
s.pop();
}
}
break;
case '}':{
if(s.top() != '{'){
flag = 1;

} else{
s.pop();
}
}
break;
default:break;
}
if(flag)
break;
}

if(!flag && s.empty()){
cout<<"括号匹配成功"<<endl;
}else{
cout<<"括号匹配失败"<<endl;
}
return 0;
}

参考

关注我的微信公众号[李一二],即时看更多的文章