给定一个仅包含'(‘、’)’和’?’三种字符构成的字符串,’?’字符可以代替左括号或者右括号。请问该字符串可以代表多少种不同的合法括号序列? 提示:建议python考生使用pypy提交代码!

区块链毕设网qklbishe.com为您提供问题的解答

给定一个仅包含'(‘、’)’和’?’三种字符构成的字符串,’?’字符可以代替左括号或者右括号。请问该字符串可以代表多少种不同的合法括号序列?
提示:建议python考生使用pypy提交代码!

s = input()
n = len(s)
if s[0] == ‘)’:
    print(0)
else:
    dp = [[0 for _ in range(n)] for _ in range(n)]
    dp[0][1] = 1
    for i in range(1, n):
        if s[i] == ‘(‘ or s[i] == ‘?’:
            for j in range(1, n):
                if j > i+1 or j > n-i-1:
                    break
                dp[i][j] += dp[i-1][j-1]
                dp[i][j] %= (1e9+7)
        if s[i] == ‘)’ or s[i] == ‘?’:
            for j in range(0,n-1):
                if j > i+1 or j > n-i-1:
                    break
                dp[i][j] += dp[i-1][j+1]
                dp[i][j] %= (1e9+7)
       

    print(int(dp[n-1][0]))

04:36
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2010;
const int mod=1e9+7;

int main() {
    string s; cin>>s;
    int n=s.length();
    // 表示到i时有j个待匹配的右括号
    vector<vector<ll>>f(n+10, vector<ll>(n+10, 0));
    if(s[0]=='(‘||s[0]==’?’) f[0][1]=1;
    for(int i=1; i<n; i++){
        if(s[i]=='(‘||s[i]==’?’){
            for(int j=1; j<n; j++){
                f[i][j]+=f[i-1][j-1];
                f[i][j]%=mod;
            }
        }
        if(s[i]==’)’||s[i]==’?’){
            for(int j=0; j<n-1; j++){
                f[i][j]+=f[i-1][j+1];
                f[i][j]%=mod;
            }
        }
    }
    cout<<f[n-1][0]<<endl;
}
// 64 位输出请用 printf("%lld")

54:02

以上就是关于问题给定一个仅包含'(‘、’)’和’?’三种字符构成的字符串,’?’字符可以代替左括号或者右括号。请问该字符串可以代表多少种不同的合法括号序列?
提示:建议python考生使用pypy提交代码!的答案

欢迎关注区块链毕设网-
专业区块链毕业设计成品源码,定制。

区块链NFT链游项目方科学家脚本开发培训

承接区块链项目定制开发

微信:btc9767

QQ :1330797917

TELEGRAM: BTCOK9

承接区块链项目定制开发


qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台-javagopython毕设 » 给定一个仅包含'(‘、’)’和’?’三种字符构成的字符串,’?’字符可以代替左括号或者右括号。请问该字符串可以代表多少种不同的合法括号序列? 提示:建议python考生使用pypy提交代码!