首页 > 试题广场 >

括号匹配方案

[编程题]括号匹配方案
  • 热度指数：68 时间限制：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

输入

(((())))

输出

24
算法知识视频讲解
添加回答
牛客198654177号头像 牛客198654177号 
#include <iostream>
#include <cstring>
#include <stack>
 using namespace std;
int main()
{
    string s;
    stack<char> st;
    int res = 1;
    cin >> s;
    if (s.size() == 0)
    {    cout << 0;
                return 0;
        }
    for (int i = 0; i < s.size(); i++)
    {
        if ( s[i] == '(' )
            st.push('(');
        else if( s[i] == ')' )
        {
            res *= s.size();
            st.pop();
        }
    }
    cout << res;
        return 0;
}
题目描述左括号看作相同，右括号看作不同；因此使用栈，将左括号看作不同，右括号看作相同，可以得到一样的结果。

发表于 2021-03-26 20:40:58 回复(0)
十月围城丶头像 十月围城丶 
#include <iostream>
#include <cstring>
#include <stack>

using namespace std;

int main()
{
    string str;
    stack<char> stk;
    int result = 1;
    cin >> str;
    for (int i = 0; i < str.size(); ++i) {
        if(str[i] == '(')
        {
            stk.push(str[i]);
        }
        if(str[i] == ')')
        {
            int count = stk.size();
            result *= count;
            stk.pop();
        }
    }
    cout << result;

    return 0;
}


发表于 2019-08-24 15:03:53 回复(0)
ThomasWangEcpkn头像 ThomasWangEcpkn
比较笨的方法：栈判断删除一个右括号是否合法，如果合法再用递归计数，不用字典会有一个超时
python3:
whileTrue:
    try:
        s =input()
        d =dict()
        defisLegal(s):
            stack =[]
            fori ins:
                ifi =='(':
                    stack.append(i)
                elifi ==')':
                    ifstack !=[]:
                        stack.pop()
                    else:
                        returnFalse
                else:
                    returnFalse
            ifstack ==[]:
                returnTrue
            else:
                returnFalse
        defcountLegalRemove(s):
            cnt =0
            ifs ind:
                returnd[s]
            iflen(s) < 2:
                return0
            ifs[0] !='(':
                return0
            ifs =='()':
                return1
            fori inrange(1, len(s)):
                ifs[i] =='(':
                    pass
                elifs[i] ==')':
                    t =s[1:i] +s[i+1:len(s)]
                    ifisLegal(t):
                        cnt +=countLegalRemove(t)
                else:
                    return0
            d[s] =cnt
            returncnt
        print(countLegalRemove(s))
    except:
        break

发表于 2018-09-20 11:25:45 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 字符串 前端工程师 算法工程师 PHP工程师 安全工程师 递归 动态规划 京东 2018 Java工程师
上传者：小小
难度：
3条回答 2112浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号