[已解决]括号匹配

柿子饼同学

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

#include<bits/stdc++.h>
using namespace std;
const int mod = 2012;
string s;
int a[100005] = {0, 1}, x = 1;
int main(){
    cin >> s;
    for(int i = 0; i < s.size(); i++){ // 循环体内是什么意思 , 不理解
        if(x <= 0) break;
        if(s[i] == ')'){
            x--;
            for(int j = 1; j <= x; j++) a[j] = (a[j]+a[j+1]) % mod;
        }
        else{
            x++;
            for(int j = x; j >= 1; j--)a[j] = (a[j]+a[j-1]) % mod;
        }
        a[x+1] = 0;
    }
    if(x==1) cout << a[1];
    else cout << 0;
    return 0; 
}

输入 :

(())

输出 :

6

解释 :

AAAA
BBBB
ABBA
BAAB
ABAB
BABA

最佳答案

月排行榜 / 总排行榜

黎羽轩

2022-7-22 09:44:48

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

bool isValid(char * s){

    int n = strlen(s); //计算字符串长度

     //定义一个栈并初始化
    char stack[n]; 
    int top = 0;

    //把s中的数据判断是否可以入栈
    for(int i = 0;i<n;i++)
    {
        char ch = s[i]; //将数据存入ch数组
    if(ch == '(' || ch == '[' || ch=='{')
    {
        //满足括号左半边的入栈
        stack[top++] = ch;
    }
    else
    {
        char ch1 = 'u'; //初始化
        if(top > 0)
        {
            //
            ch1 = stack[top-1]; 
        }
        if( (top > 0) && 
        (ch1 == '(' && ch == ')') ||
         (ch1 == '[' && ch ==']') ||
          (ch1 =='{' && ch == '}') 
          )
        {
            //出栈
            top--;
        }
        else
        {
            return false;
        }
    }
    }
    //判空
    if(top == 0)
    {
        return true;//完成
    }
    else
    {
        return false;
    }
}

跳转到最佳答案楼层

柿子饼同学

黎羽轩

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

黎羽轩

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

bool isValid(char * s){

    int n = strlen(s); //计算字符串长度

     //定义一个栈并初始化
    char stack[n]; 
    int top = 0;

    //把s中的数据判断是否可以入栈
    for(int i = 0;i<n;i++)
    {
        char ch = s[i]; //将数据存入ch数组
    if(ch == '(' || ch == '[' || ch=='{')
    {
        //满足括号左半边的入栈
        stack[top++] = ch;
    }
    else
    {
        char ch1 = 'u'; //初始化
        if(top > 0)
        {
            //
            ch1 = stack[top-1]; 
        }
        if( (top > 0) && 
        (ch1 == '(' && ch == ')') ||
         (ch1 == '[' && ch ==']') ||
          (ch1 =='{' && ch == '}') 
          )
        {
            //出栈
            top--;
        }
        else
        {
            return false;
        }
    }
    }
    //判空
    if(top == 0)
    {
        return true;//完成
    }
    else
    {
        return false;
    }
}

w.py

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

陈尚涵

这个用栈解决会更简单