括号匹配问题
1000(ms)
65535(kb)
3045 / 13375
假设表达式中允许包含两种括号:圆括号和方括号。编写一个算法判断表达式中的括号是否正确配对。
输入
由括号构成的字符串，包含”(“、”)“、”[“和”]“。
输出
如果匹配输出YES，否则输出NO。
样例输入
[([][]())]
样例输出
YES
首先是手撕链栈的用法
1 #include
2 #include
3 #include
4 #include
5 typedef char Datetype;
6 using namespace std;
7
8 typedef struct link{
9 Datetype date;
10 struct link *next;
11 }Lnode;
12
13 void Initstack(Lnode *&L)
14 {
15 L=(Lnode *)malloc(sizeof(Lnode));
16 L->next=NULL;
17 }
18
19 void destroystack(Lnode *&L)
20 {
21 Lnode *p=L,*r=p->next;
22 while(r!=NULL)
23 {
24 free(p);
25 p=r;
26 r=r->next;
27 }
28 free(p);
29 }
30
31 void push(Lnode *L , Datetype e)
32 {
33 Lnode *p;
34 p = (Lnode *)malloc(sizeof(Lnode));
35 p->date = e ;
36 p->next=L->next;
37 L->next=p;
38 }
39
40 bool stackempty(Lnode *L)
41 {
42 return(L->next==NULL);
43 }
44
45 bool pop(Lnode *&L , Datetype &e)
46 {
47 Lnode *p;
48 if(L->next==NULL)
49 return false;
50 p=L->next;
51 L->next=p->next;
52 e=p->date;
53 free(p);
54 return true;
55 }
56
57 bool gettop(Lnode *L, Datetype &e)
58 {
59 if(L->next==NULL)
60 return false;
61 e=L->next->date;
62 return true;
63 }
64
65 int main()
66 {
67 char a[1000],x;
68 cin>>a;
69 Lnode *L=NULL;
70 Initstack(L);
71 for(int i=0;i
72 {
73 if(stackempty(L)) //栈为空就直接入栈
74 {
75 push(L,a[i]);
76 }
77 else{
78 gettop(L,x);
79 if(x=='('&&a[i]==')') //配对后就出栈
80 {
81 pop(L,x);
82 }
83 else if(x=='['&&a[i]==']')
84 {
85 pop(L,x);
86 }
87 else
88 {
89 push(L,a[i]); //未配对成功就入栈
90 }
91 }
92 }
93 if(stackempty(L))
94 cout<
95 else
96 cout<
97 destroystack(L);
98 return 0;
99 }
然后是利用STL的做法
1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 using namespace std;
8 char arr;
9 int main()
10 {
11 stackst;
12 while(scanf("%c",&arr)&&arr!='\n')
13 {
14 if(st.empty())
15 {
16 st.push(arr);
17 continue;
18 }
19 if((arr==']'&&st.top()=='[')||(arr==')'&&st.top()=='('))
20 st.pop();
21 else
22 st.push(arr);
23 }
24 if(st.empty())
25 cout<
26 else
27 cout<
28 }
标签：arr,include,oj,962,NULL,next,st,swust,Lnode
来源： /Iwpml-595/p/10676323.html
