首页 > 试题广场 >

括号匹配方案

[编程题]括号匹配方案

热度指数：564 时间限制：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

输入

(((())))

输出

算法知识视频讲解

duo-re-mi

var arr = readline();
function getRes (arr) {
    for(var i=0; i<arr.length; i++) {

        if(arr[i] == ')') {
            var str = "";
            if(i=='1') {
                str += arr.substring(2);
                return i*getRes(str);
            }
           str = arr.slice(0,i-1) + arr.slice(i+1, arr.length);
           return i*getRes(str);
        }
    }
    if(arr == "") {
            return 1;
    }
}
var res = getRes(arr);
print(res);

发表于 2018-05-23 10:35:49 回复(6)

Benjaminpcm

python3版本

有多少个'('就会用多少个')'，通过'('来确定出')'的个数

import sys
s = sys.stdin.readline()
res = 1 
for i in s: 
    if i == '(':
        stack.append(i)
    else:
        res *= len(stack)
        stack.pop() print(res)
print(res)

编辑于 2018-12-29 17:44:06 回复(0)

Python

立意悖反

# 楼上正解，Python版本
import sys
s = sys.stdin.readline().strip()
res = 1
stack = []
for i in s:
    if i == '(':
        stack.append(i)
    else:
        res *= len(stack)
        stack.pop() 
print res

编辑于 2018-10-19 01:13:08 回复(0)

不愿停

var line = readline().split('');
var count=1;
while(line.length) {
    var i = line.indexOf(')');
    count *= i;
    line.splice(i-1,2);
}
print(count);

编辑于 2018-09-10 16:00:10 回复(1)