[已解决]括号匹配

柿子饼同学

求助 , 题解看不懂 , 求解释和思路

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. const int mod = 2012;
   
4. string s;
   
5. int a[100005] = {0, 1}, x = 1;
   
6. int main(){
   
7.     cin >> s;
   
8.     for(int i = 0; i < s.size(); i++){ // 循环体内是什么意思 , 不理解
   
9.         if(x <= 0) break;
   
10.         if(s[i] == ')'){
    
11.             x--;
    
12.             for(int j = 1; j <= x; j++) a[j] = (a[j]+a[j+1]) % mod;
    
13.         }
    
14.         else{
    
15.             x++;
    
16.             for(int j = x; j >= 1; j--)a[j] = (a[j]+a[j-1]) % mod;
    
17.         }
    
18.         a[x+1] = 0;
    
19.     }
    
20.     if(x==1) cout << a[1];
    
21.     else cout << 0;
    
22.     return 0;
    
23. }

复制代码

输入 :

1. (())

复制代码

输出 :

1. 6

复制代码

解释 :

1. AAAA
   
2. BBBB
   
3. ABBA
   
4. BAAB
   
5. ABAB
   
6. BABA

复制代码

最佳答案

月排行榜 / 总排行榜

黎羽轩

2022-7-22 09:44:48

黎羽轩 发表于 2022-7-17 07:40
括号匹配的原理就是
一个算法→括号匹配
它首先申请一个数组（也可以是栈）

1. bool isValid(char * s){
   
2. 
   
3.     int n = strlen(s); //计算字符串长度
   
4. 
   
5.      //定义一个栈并初始化
   
6.     char stack[n];
   
7.     int top = 0;
   
8. 
   
9.     //把s中的数据判断是否可以入栈
   
10.     for(int i = 0;i<n;i++)
    
11.     {
    
12.         char ch = s[i]; //将数据存入ch数组
    
13.     if(ch == '(' || ch == '[' || ch=='{')
    
14.     {
    
15.         //满足括号左半边的入栈
    
16.         stack[top++] = ch;
    
17.     }
    
18.     else
    
19.     {
    
20.         char ch1 = 'u'; //初始化
    
21.         if(top > 0)
    
22.         {
    
23.             //
    
24.             ch1 = stack[top-1];
    
25.         }
    
26.         if( (top > 0) &&
    
27.         (ch1 == '(' && ch == ')') ||
    
28.          (ch1 == '[' && ch ==']') ||
    
29.           (ch1 =='{' && ch == '}')
    
30.           )
    
31.         {
    
32.             //出栈
    
33.             top--;
    
34.         }
    
35.         else
    
36.         {
    
37.             return false;
    
38.         }
    
39.     }
    
40.     }
    
41.     //判空
    
42.     if(top == 0)
    
43.     {
    
44.         return true;//完成
    
45.     }
    
46.     else
    
47.     {
    
48.         return false;
    
49.     }
    
50. }

复制代码

跳转到最佳答案楼层

柿子饼同学

黎羽轩

括号匹配的原理就是
一个算法→括号匹配
它首先申请一个数组（也可以是栈）
然后，遍历你那个有括号数组，
如果是左边的话就入栈
如果是右边的话就出栈并与最近入栈的左括号进行匹配
直至比较匹配完成
（我的理解）

黎羽轩

黎羽轩 发表于 2022-7-17 07:40
括号匹配的原理就是
一个算法→括号匹配
它首先申请一个数组（也可以是栈）

1. bool isValid(char * s){
   
2. 
   
3.     int n = strlen(s); //计算字符串长度
   
4. 
   
5.      //定义一个栈并初始化
   
6.     char stack[n];
   
7.     int top = 0;
   
8. 
   
9.     //把s中的数据判断是否可以入栈
   
10.     for(int i = 0;i<n;i++)
    
11.     {
    
12.         char ch = s[i]; //将数据存入ch数组
    
13.     if(ch == '(' || ch == '[' || ch=='{')
    
14.     {
    
15.         //满足括号左半边的入栈
    
16.         stack[top++] = ch;
    
17.     }
    
18.     else
    
19.     {
    
20.         char ch1 = 'u'; //初始化
    
21.         if(top > 0)
    
22.         {
    
23.             //
    
24.             ch1 = stack[top-1];
    
25.         }
    
26.         if( (top > 0) &&
    
27.         (ch1 == '(' && ch == ')') ||
    
28.          (ch1 == '[' && ch ==']') ||
    
29.           (ch1 =='{' && ch == '}')
    
30.           )
    
31.         {
    
32.             //出栈
    
33.             top--;
    
34.         }
    
35.         else
    
36.         {
    
37.             return false;
    
38.         }
    
39.     }
    
40.     }
    
41.     //判空
    
42.     if(top == 0)
    
43.     {
    
44.         return true;//完成
    
45.     }
    
46.     else
    
47.     {
    
48.         return false;
    
49.     }
    
50. }

复制代码

w.py

mmm...看不懂，渣渣一枚

陈尚涵

这个用栈解决会更简单