给定一个仅包含'(‘、’)’和’?’三种字符构成的字符串，’?’字符可以代替左括号或者右括号。请问该字符串可以代表多少种不同的合法括号序列？提示：建议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")