题目分析:
因为输入的多个括号是符合规则的,所以第一个字符一定是‘(’,先将其放入定义的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; }