就像这样

源代码如下

#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
const int mod = 1000000007;
int len, p[705];
int dp[75][75][3][3];
string s;
stack <int> st;
void dfs(int l, int r)
{
	if(l + 1 == r)
	{
		dp[l][r][0][2] = dp[l][r][2][0] = dp[l][r][0][1] = dp[l][r][1][0] = 1;
		return ;
	}
	else if(p[l] == r)
	{
		dfs(l + 1, r - 1);
		for(int i = 0; i <= 2; i++)
		{
			for(int j = 0; j <= 2; j++)
			{
				if(i != 1) dp[l][r][1][0] = (dp[l][r][1][0] + dp[l + 1][r - 1][i][j]) % mod;
				if(j != 1) dp[l][r][0][1] = (dp[l][r][0][1] + dp[l + 1][r - 1][i][j]) % mod;
				if(i != 2) dp[l][r][2][0] = (dp[l][r][2][0] + dp[l + 1][r - 1][i][j]) % mod;
				if(j != 2) dp[l][r][0][2] = (dp[l][r][0][2] + dp[l + 1][r - 1][i][j]) % mod;
			}
		}
	}
	else
	{
		dfs(l, p[l]);
		dfs(p[l] + 1, r);
		for(int i = 0; i <= 2; i++)
		{
			for(int j = 0; j <= 2; j++)
			{
				for(int k = 0; k <= 2; k++)
				{
					for(int x = 0; x <= 2; x++)
					{
						if((j == 2 && k == 2) || (j == 1 && k == 1))
						{
							continue;
						} 
						dp[l][r][i][x] = (dp[l][r][i][x] + dp[l][p[l]][i][j] * dp[p[l] + 1][r][k][x]) % mod;
					}
				}
			}
		}
	}
	return ;
}
int main()
{
	ios::sync_with_stdio(false);
	cin >> s;
	len = s.size();
	s = ' ' + s;
	for(int i = 1; i <= len; i++)
	{
		if(s[i] == '(')
		{
			st.push(i);
		}
		else if(s[i] == ')')
		{
			p[st.top()] = i;
			p[i] = st.top();
			st.pop();
		}
	}
	dfs(1, len);
	int ans = 0;
	for(int i = 0; i <= 2; i++)
	{
		for(int j = 0; j <= 2; j++)
		{
//			cout << dp[1][len][i][j] << " ";
			ans = (ans + dp[1][len][i][j]) % mod;
		}
//		cout << '\n';
	}
	cout << ans;
	return 0;
}
//////////////////////////////////////