C. Recover an RBS (parenthesis sequence, thinking)

Educational Codeforces Round 132 (Rated for Div. 2)

Problem

Give a sequence of parentheses . Now replace a few of these characters with '?'. ask ： Is there only one legal solution , So that the sequence can be translated into the correct arithmetic expression .
Input guarantees that at least one legal scheme exists .

Solution

cnt： Indicates the number of left parentheses
num： Indicates the currently undetermined number of question marks
Traverse from left to right , See code for details

Code

int main()
{
    
	int T; cin >> T;
	while (T--)
	{
    
		string s; cin >> s;
		int len = s.size();
		int cnt = 0, num = 0;
		s[0] = '(';
		for (int i = 0; i < len; i++)
		{
    
			if (s[i] == '(') cnt++;
			else if (s[i] == ')')
			{
    
				cnt--;
				if (cnt < 0) cnt++, num--;// The previous undetermined question mark needs to be determined as  '('
			}
			else num++;

			if (cnt == 0 && num == 1) cnt = 1, num = 0;// Similar to the parenthesis sequence, the first one is  '?',  therefore '?'  It should be determined as  '('
		}

		cout << (cnt == num ? "YES\n" : "NO\n");
	}
}