Page Contents
A. Regular Bracket Sequence SOLUTION CodeForces
Educational Codeforces Round 101 (Rated for Div. 2)
A bracket sequence is called regular if it is possible to obtain correct arithmetic expression by inserting characters + and 1 into this sequence. For example, sequences (())(), () and (()(())) are regular, while )(, (() and (()))( are not. Let’s call a regular bracket sequence “RBS”.
You are given a sequence s of n characters (, ), and/or ?. There is exactly one character ( and exactly one character ) in this sequence.
You have to replace every character ? with either ) or ( (different characters ? can be replaced with different brackets). You cannot reorder the characters, remove them, insert other characters, and each ? must be replaced.
Determine if it is possible to obtain an RBS after these replacements.
Input
The first line contains one integer t (1≤t≤1000) — the number of test cases.
Each test case consists of one line containing s (2≤|s|≤100) — a sequence of characters (, ), and/or ?. There is exactly one character ( and exactly one character ) in this sequence.
Output
For each test case, print YES if it is possible to obtain a regular bracket sequence, or NO otherwise}.
You may print each letter in any case (for example, YES, Yes, yes, yEs will all be recognized as positive answer).
Example
inputCopy
5
()
(?)
(??)
??()
)?(?
outputCopy
YES
NO
YES
YES
NO
Note
In the first test case, the sequence is already an RBS.
In the third test case, you can obtain an RBS as follows: ()() or (()).
In the fourth test case, you can obtain an RBS as follows: ()().
SOLUTION:
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
int t;
cin>>t;
while(t–){
string s;
cin>>s;
int n=s.length();
if(n%2||s[0]==’)’||s[n-1]=='(‘) cout<<“NOn”;
else cout<<“YESn”;
}
}
RELATED :
A. Regular Bracket Sequence SOLUTION CodeForces
B. Red and Blue SOLUTION CodeForces
C. Building a Fence SOLUTION CodeForces
D. Ceil Divisions SOLUTION CodeForces
E. A Bit Similar SOLUTION CodeForces
F. Power Sockets SOLUTION CodeForces
