Monday 10 July 2017

UVA 673 - Parentheses Balance

problem:
You are given a string consisting of parentheses () and []. A string of this type is said to be correct:
(a) if it is the empty string
(b) if A and B are correct, AB is correct,
(c) if A is correct, (A) and [A] is correct.
Write a program that takes a sequence of strings of this type and check their correctness. Your
program can assume that the maximum string length is 128.
Input
The file contains a positive integer n and a sequence of n strings of parentheses ‘()’ and ‘[]’, one string
a line.
Output
A sequence of ‘Yes’ or ‘No’ on the output file.
Sample Input
3
([])
(([()])))
([()[]()])()
Sample Output
Yes
No

Yes
My accepted code is given below:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    long long i,j,n,l,f;
    cin>>n;

    getchar();
    while(n--)
    {

        getline(cin,s);
        //cout<<"x="<<s<<endl;
 l=s.length();
        stack<char>q;
        if(l%2!=0)
            cout<<"No"<<endl;

        else
        {
            f=0;

            for(i=0; i<l; i++)
            {
                if(s[i]=='('||s[i]=='[')
                {
                    //cout<<"1";
                    q.push(s[i]);
                }
               else if(!q.empty()&&s[i]==')'&&q.top()=='(')
                {
                   // cout<<"2";
                    q.pop();
                }
                    else if(!q.empty()&&s[i]==']'&&q.top()=='[')
                {
                    //cout<<"3";
                    q.pop();
                }
                else
                {
                    q.push(s[i]);
                }
            }

            if(q.empty())
                cout<<"Yes"<<endl;
            else
                cout<<"No"<<endl;
        }
    }

    return 0;
}

No comments:

Post a Comment