括号匹配问题

1000(ms) 65535(kb) 3045 / 13375

假设表达式中允许包含两种括号:圆括号和方括号。编写一个算法判断表达式中的括号是否正确配对。

输入

由括号构成的字符串，包含”（“、”）“、”[“和”]“。

输出

如果匹配输出YES，否则输出NO。

样例输入

[([][]())]

样例输出

YES 


首先是手撕链栈的用法

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 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<strlen(a);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<<"YES";
95     else
96         cout<<"NO";
97     destroystack(L);
98     return 0;
99 }

 

然后是利用STL的做法

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iostream>
 5 #include<stack>
 6 #include<string>
 7 using namespace std;
 8 char arr;
 9 int main()
10 {
11     stack<char>st;
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<<"YES";
26     else
27         cout<<"NO";
28 }