问题 A: Star in Parentheses
时间限制: 1 Sec 内存限制: 128 MB
提交: 240 解决: 99
[提交] [状态] [命题人:admin]
题目描述
You are given a string S, which is balanced parentheses with a star symbol '*' inserted.
Any balanced parentheses can be constructed using the following rules:
An empty string is balanced.
Concatenation of two balanced parentheses is balanced.
If T is balanced parentheses, concatenation of '(', T, and ')' in this order is balanced.
For example, '()()' and '(()())' are balanced parentheses. ')(' and ')()(()' are not balanced parentheses.
Your task is to count how many matching pairs of parentheses surround the star.
Let Si be the i-th character of a string S. The pair of Sl and Sr (l<r) is called a matching pair of parentheses if Sl is '(', Sr is ')' and the surrounded string by them is balanced when ignoring a star symbol.
输入
The input consists of a single test case formatted as follows.
S
S is balanced parentheses with exactly one '*' inserted somewhere. The length of S is between 1 and 100, inclusive.
输出
Print the answer in one line.
样例输入
复制样例数据
((*)())
样例输出
2
这题的AC代码让我很难受，我的思路的先找出*左边未被匹配的左括号和*右边未被匹配的右括号，然后看最多能匹配多少个。（WA）
然后就换成求*左边未被匹配的左括号，只有右边出现右括号就先和左边未被匹配的左括号匹配，这样就AC了，难受~
#include<bits/stdc++.h> using namespace std; const int maxn=3*1e5+10;int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);string t;cin>>t;int len=t.length();int lc=0,rc=0,ar=0,rl;//lc左边未匹配的lc的数量，右边未匹配的rc的数量 bool flag=true; //true表示*的左边，false表示*的右边 for(int i=0;i<len;i++){if(t[i]=='*'){flag=false; }else if(flag){if(t[i]=='('){lc++;}else{if(lc) lc--;}}else{if(t[i]=='('){rl++;}else{if(lc){ar++; lc--;}else if(rc){rc--;}}}}printf("%d\n",ar);return 0; }