首页 > 试题广场 >

括号匹配方案

[编程题]括号匹配方案

热度指数：37 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

合法的括号匹配序列被定义为:
1. 空串""是合法的括号序列
2. 如果"X"和"Y"是合法的序列,那么"XY"也是一个合法的括号序列
3. 如果"X"是一个合法的序列,那么"(X)"也是一个合法的括号序列
4. 每个合法的括号序列都可以由上面的规则生成
例如"", "()", "()()()", "(()())", "(((())))"都是合法的。东东现在有一个合法的括号序列s,一次移除操作分为两步:
1. 移除序列s中第一个左括号
2. 移除序列s中任意一个右括号.保证操作之后s还是一个合法的括号序列
东东现在想知道使用上述的移除操作有多少种方案可以把序列s变为空
如果两个方案中有一次移除操作移除的是不同的右括号就认为是不同的方案。
例如: s = "()()()()()",输出1, 因为每次都只能选择被移除的左括号所相邻的右括号.
s = "(((())))",输出24, 第一次有4种情况, 第二次有3种情况, ... ,依次类推, 4 * 3 * 2 * 1 = 24

输入描述:

输入包括一行,一个合法的括号序列s,序列长度length(2 ≤ length ≤ 20).

输出描述:

输出一个整数,表示方案数

示例1

输入

(((())))

输出

算法知识视频讲解

C/C++

牛油1111

#include<stdio.h>
#include<string.h>
int main(){
    long long int sum = 1;
    int n = 0;
    char str[30];
    gets(str);
    int l = strlen(str);
    for(int i = l - 1; i >= 0; i--){
        if(str[i] == ')'){
            n++;
            sum *= n;
        }
        else
            n--;
    }
    printf("%lld", sum);
}

从字符串右侧开始计数，n表示是第几个连续的右括号，sum表示最后输出的结果数，遇左括号则抵消减少一个右括号。一开始我是从左侧开始计数，遇到左括号则n清零，后来发现这样做对于（（）（（）））这种情况是不对的

编辑于 2018-08-26 20:29:34 回复(2)

牛客8751634号

从右边开始计数，遇到右括号，加一，遇到左括号，开始计总数。
#include <iostream>
#include <string>
using namespace std;

int main()
{
    string str;
    while(cin>>str){
        int len = str.length();
        int right = 0;
        long long res = 1;
        for(int i = len -1;i>=0;--i){
            if(str[i] == ')')
                ++right;
            else{
                res = res*right%10000000007ll;
                --right;
            }
        }
        cout << res <<endl;
    }
    return 0;
}

发表于 2018-07-14 16:36:12 回复(0)