题目分析:
因为输入的多个括号是符合规则的,所以第一个字符一定是‘(’,先将其放入定义的stack中,在进行for循环中如果遇到‘(’就将其放入stack中,如果是‘)’,就抵消掉一个‘(’,并且sum的值*stack中元素的多少,再用pop将一个‘(’删除。
可以理解为如果遇到右括号,则这个右括号可以消去一个左括号,每有一个左括号就多一种选择,选择完后,请删掉一个左括号。
AC代码:
#include <cstdio>
#include <iostream>
#include <stack>
#include <string>
#include <cstring>
using namespace std;
const int mod = 1e9+7;
int main ()
{
char s[2505];
int sum=1;
cin >> s;
stack<char>a;
a.push(s[0]);
for (int i=1;i<strlen(s);i++)
{
if(s[i]=='(')
{
a.push(s[i]);
}
else
{
sum=(sum * a.size()) % mod;
a.pop();
}
}
cout << sum << endl;
return 0;
}
第二种方法:
#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
typedef long long ll;
ll mod = 1000000007;
int main()
{
string s;
cin >> s;
int len = s.length();
ll sum=1;
ll ans = 1;
for (int i=1;i<len;i++)
{
if(s[i]=='(') sum++;
else
{
ans = ans * sum % mod;
sum--;
}
}
cout << ans << endl;
return 0;
}


京公网安备 11010502036488号