Star in Parentheses

题目描述

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

题意+题解

题意：有多少个有效的括号对能把星号包起来，如果能和近的消掉的括号不是有效的

如果星号左边出现（ , l ++ ，

星号左边出现 ） ，如果 l !=0，l--;

如果星号右边出现（ , pl ++ ，

星号右边出现 ） ，如果 pl !=0，l--; 否则r++

那么l 和 r之间的最小值就是括号对的个数

代码

#include
    
     using namespace std;#define pb push_back#define mp make_pair#define rep(i,a,n) for(int i=a;i
     
       P;const int INF =0x3f3f3f3f;const int inf =0x3f3f3f3f;const int mod = 1e9+7;const int MAXN = 105;const int maxn =1000010;using namespace std;char s[15000];int main(){  scanf("%s",s);  int flag = 0 ;  int r = 0;  int l = 0;  int pl = 0;  for(int i = 0; i < strlen(s);i++){    if(s[i] == '*') {      flag = 1;    }    if(!flag && s[i] =='(')      l++;    else if(!flag && s[i] ==')'){      if(l) l--;    }    else if(flag && s[i] == '('){      pl++;    }    else if(flag && s[i] == ')'){      if(pl) pl --;      else r++;    }  }  printf("%d\n",l < r ? l : r);}