Problem Link: https://onlinejudge.org/external/6/673.pdf
Note:
This can be solved using different data structures and logic. I have used Stack to approach the problem.
Solution:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| Author: Arunima Mandal | |
| Updated Date: 06.16.2020 | |
| */ | |
| #include <bits/stdc++.h> | |
| #define pf printf | |
| #define sf(a) scanf("%d",&a) | |
| #define sfl(a) scanf("%lld",&a) | |
| #define sff(a,b) scanf("%d %d",&a,&b) | |
| #define sffl(a,b) scanf("%lld %lld",&a,&b) | |
| #define sfff(a,b,c) scanf("%d %d %d",&a,&b,&c) | |
| #define sfffl(a,b,c) scanf("%lld %lld %lld",&a,&b,&c) | |
| #define sffff(a,b,c,d) scanf("%d %d %d %d",&a,&b,&c,&d) | |
| #define sffffl(a,b,c,d) scanf("%lld %lld %lld %lld",&a,&b,&c,&d) | |
| #define sfffff(a,b,c,d,e) scanf("%d %d %d %d %d",&a,&b,&c,&d,&e) | |
| #define sfffffl(a,b,c,d,e) scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&d,&e) | |
| #define sfc(a) scanf("%c",&a) | |
| #define ms(a,b) memset(a,b,sizeof(a)) | |
| #define pb(a) push_back(a) | |
| #define db double | |
| #define ll long long | |
| #define ull unsigned long long | |
| #define pii pair<int,int> | |
| #define pll pair<long,long> | |
| #define ff first | |
| #define ss second | |
| #define sz(x) (int)x.size() | |
| #define all(x) x.begin(),x.end() | |
| #define CIN ios_base::sync_with_stdio(0); cin.tie(0) | |
| #define max3(a, b, c) max(a, b) > max(b, c) ? max(a, b) : max(b, c) | |
| #define min3(a, b, c) min(a, b) < min(b, c) ? min(a, b) : min(b, c) | |
| #define for0(i,n) for(int i=0;i<n;i++) | |
| #define for1(i,n) for(int i=1;i<=n;i++) | |
| #define forrev(i,n) for(int i=n-1; i>=0; i--) | |
| #define forab(i,a,b) for(int i=a;i<=b;i++) | |
| #define forba(i,b,a) for(int i=b;i>=a;i--) | |
| #define stlloop(x) for(__typeof(x.begin()) it=x.begin();it!=x.end();it++) | |
| #define gcd(a, b) __gcd(a, b) | |
| #define lcm(a, b) ((a)*((b)/gcd(a,b))) | |
| #define case1(z) cout<<"Case "<<z<<": " | |
| #define case2(z) printf("Case %d: ",z) | |
| #define PI acos(-1) //3.14159265358979323846264338328 | |
| #define valid(tx,ty) tx>=0 && tx<row && ty>=0 && ty<col | |
| #define intlim 2147483648 | |
| #define MAX 1000006 | |
| #define inf 100000008 | |
| ll power(int n,int p) | |
| { | |
| ll ans=1; | |
| for1(i,p) ans*=n; | |
| return ans; | |
| } | |
| ll m=1000001; | |
| ll bigmod(ll n,ll p) | |
| { | |
| if(p==0) return 1; | |
| else if(p%2==0) | |
| { | |
| ll x=(bigmod(n,p/2))%m; | |
| return (x*x)%m; | |
| } | |
| else return ((n%m)*(bigmod(n,p-1)%m))%m; | |
| } | |
| /*------------------------------Graph Moves----------------------------*/ | |
| //const int fx[]={+1,-1,+0,+0}; | |
| //const int fy[]={+0,+0,+1,-1}; | |
| //const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move | |
| //const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move | |
| //const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move | |
| //const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move | |
| /*---------------------------------------------------------------------*/ | |
| using namespace std; | |
| stack<char> st; | |
| string s; | |
| int main() | |
| { | |
| // CIN; //if getline() is present, it can't be used. | |
| // freopen("in.txt","r",stdin); | |
| // freopen("out.txt","w",stdout); | |
| int t,d; | |
| sf(t); | |
| getchar(); | |
| for0(z,t) | |
| { | |
| getline(cin,s); | |
| d=0; | |
| for0(i,sz(s)) | |
| { | |
| if(s[i]=='(' || s[i]=='{' || s[i]=='[') | |
| { | |
| st.push(s[i]); | |
| } | |
| else if(s[i]==' ') continue; | |
| else | |
| { | |
| if(!st.empty()) | |
| { | |
| char ch=st.top(); | |
| if((ch=='(' && s[i]==')') || (ch=='{' && s[i]=='}') || (ch=='[' && s[i]==']')) | |
| { | |
| st.pop(); | |
| } | |
| else break; | |
| } | |
| else {d=1; break;} //there is nothing left in stack to compare with. | |
| } | |
| } | |
| if(!d && st.empty()) pf("Yes\n"); | |
| else | |
| { | |
| pf("No\n"); | |
| while(!st.empty()) st.pop(); | |
| } | |
| } | |
| return 0; | |
| } |
Fall out, Codes! 