673 - Parentheses Balance

All about problems in Volume 6. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 673 - Parentheses Balance

Post by brianfry713 » Thu Oct 23, 2014 9:04 pm

Don't use a package. Use class Main.
Check input and AC output for thousands of problems on uDebug!

imran_12
New poster
Posts: 9
Joined: Fri Sep 19, 2014 7:56 am

Re: 673 - Parentheses Balance(why getting WA?? )

Post by imran_12 » Mon Dec 08, 2014 7:10 pm

here is my code....i dunno why i m getting WA??
plz somebody help.... :( :(

Code: Select all

#include<stdio.h>
#include<string.h>
int main()
{
    char a[130],c;
    int n,j,i,flag,flagn,b;
    while(scanf("%d",&n)==1)
    {
        fflush(stdin);
        for(j=1;j<=n;j++)
        {
            flag=0;
            flagn=0;
        gets(a);
        b=strlen(a);
        for(i=0;i<b;i++)
        {
            if(a[i]=='(')
            {
                flag++;
            }
            if(a[i]==')')
            {
                flag--;
            }
            if(a[i]=='[')
            {
                flagn++;
            }
            if(a[i]==']')
            {
                flagn--;
            }
        }
        if(flag==0 && flagn==0 && (a[0]=='(' && a[b-1]==')') || (a[0]=='[' && a[b-1]==']'))
        {
            printf("Yes\n");
        }
        else
        {
            printf("No\n");
        }
        fflush(stdin);
        }
    }
    return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 673 - Parentheses Balance

Post by brianfry713 » Mon Dec 08, 2014 10:31 pm

Don't use fflush(stdin);
Check input and AC output for thousands of problems on uDebug!

mohdali231993
New poster
Posts: 11
Joined: Sun Nov 09, 2014 6:46 pm

Re: 673 - Parentheses Balance

Post by mohdali231993 » Sat Dec 20, 2014 10:29 pm

Code: Select all

#include<iostream>
#include<stack>
#include<string>
using namespace std;
typedef unsigned int uint;
int main()
{
    uint t, flag = 1, len,i;
    char c, cc;
    string ss;
    cin>>t;
    while(t)
    {    
        flag=1;stack<char> s;i=0;
        cin>>ss;
        len = ss.length();
        while(i < len)    
        {
                
            c = ss[i];  
            if((int)c == 40 || (int)c == 91)
                {s.push(c);   }
            else 
            {   
                cc = s.top();
                if((int)cc-(int)c <= 5)
                  {s.pop();}
                else
                  {flag=0;break;}       
            }   
            i++;
                
        }
        if(!s.empty()) flag=0;
        if(flag) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
        t--;    
    }        
    return 0;
}    
I am getting a runtime error on this code
Plz help

mohdali231993
New poster
Posts: 11
Joined: Sun Nov 09, 2014 6:46 pm

Re: 673 - Parentheses Balance

Post by mohdali231993 » Sat Dec 20, 2014 11:53 pm

Code: Select all

#include<iostream>
#include<stack>
#include<string>
using namespace std;
typedef unsigned int uint;
int main()
{
    uint t, flag = 1, len,i;
    char c, cc;
    cin>>t;
    while(t)
    {    
        flag=1;stack<char> s;string ss;i=0;
        cin>>ss;
        len = ss.length();
        while(i < len)    
        {
            c = ss[i];  
            if((int)c == 40 || (int)c == 91)
                {s.push(c);}
            else 
            {   
                if(!s.empty())
                {
                 cc = s.top();
                 if(((int)c-(int)cc <= 2) && ((int)c-(int)cc > 0))
                 {s.pop();}
                 else
                 {flag=0;break;}
                }
                  else
                  {flag=0;break;}
                       
            }   
            i++;
                
        }
        if(!s.empty()) {flag=0;}
        if(flag) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
        t--;    
    }        
    return 0;
}    
    
    
    

Ignore the last question
This code is giving WA
Help me out guys

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 673 - Parentheses Balance

Post by lighted » Sun Dec 21, 2014 9:42 am

Try to check input in this thread before posting
brianfry713 wrote:You need to parse the input line by line as a line may be blank.

Input:

Code: Select all

4

([])
(([()])))
([()[]()])()
Output should be:

Code: Select all

Yes
Yes
No
Yes
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

mohdali231993
New poster
Posts: 11
Joined: Sun Nov 09, 2014 6:46 pm

Re: 673 - Parentheses Balance

Post by mohdali231993 » Sun Dec 21, 2014 11:40 am

@lighted
Thanks i figured it out
and sorry to have bothered you

littleaich
New poster
Posts: 2
Joined: Fri Jan 16, 2015 8:17 pm

Re: 673 - Parentheses Balance

Post by littleaich » Fri Jan 16, 2015 8:25 pm

Dear Experts,

I have read all the discussions on this problem posted here and my code can handle the discussed problems correctly. But still I am getting wrong answer. Can anybody give any hint or some tricky test cases other than the already posted ones. Here is my code:

Code: Select all

#include <iostream>
#include <string>
#include <algorithm> 

using namespace std;

int main(void)
{
	int n, len, count, front, back;
	bool matching;
	char backTracker;
	bool getFront = false;
	cin >> n;
	fflush(stdin);
	string line;
	
	while(n!=0)
	{
		getline(cin,line);
		line.erase(std::remove(line.begin(), line.end(), ' '), line.end());
		count = 0;
		matching = true;
		len = line.length();
		if(line.empty())
			matching = true;
		else if((len%2!=0) | (line[0]==')') | 
			(line[0]==']') | (line[len-1]=='(') | (line[len-1]=='['))
			matching = false;
		else
		{
			front = len;
			while(front>0)
			{
				if(line[front-1]=='(')
				{	
					backTracker = ')';
					getFront = true;
				}	
				else if(line[front-1]=='[')
				{
					backTracker = ']';
					getFront = true;
				}
				
				if(getFront)
				{
					back = front + 1;
					while(1)
					{
						if(line[back-1]==')'| line[back-1]==']')
						{
							if(line[back-1]!=backTracker)
							{
								matching = false;
								break;
							}
							else
							{
								line[back-1]='v'; // already visited
								break;
							}
						}
						else
						{
							back++;
							if(back>len)
							{
								break;
								matching = false;
							}
						}
					}
				}

				getFront = false;

				if(!matching)
					break;
				front--;
			}
		}

		if(matching)
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
		n--;
		line.clear();

	}

	return 0;
}
Last edited by brianfry713 on Fri Jan 16, 2015 10:34 pm, edited 1 time in total.
Reason: Added code blocks

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 673 - Parentheses Balance

Post by brianfry713 » Sat Jan 17, 2015 12:54 am

Don't use fflush(stdin);
Check input and AC output for thousands of problems on uDebug!

littleaich
New poster
Posts: 2
Joined: Fri Jan 16, 2015 8:17 pm

Re: 673 - Parentheses Balance

Post by littleaich » Sat Jan 17, 2015 12:08 pm

Thank you @brianfry713. The problem was with fflush(stdin). Now it's accepted.

NAbdulla
New poster
Posts: 31
Joined: Wed Jul 30, 2014 3:40 pm
Contact:

673 - Parentheses Balance WA

Post by NAbdulla » Tue Jan 20, 2015 6:48 pm

Please help
Getting WA

removed after Accepted

arnab5574
New poster
Posts: 1
Joined: Sat Apr 25, 2015 11:13 am

Re: 673 - Parentheses Balance

Post by arnab5574 » Sat Apr 25, 2015 11:43 am

Why am i getting runtime error for this code?? plz help

Code: Select all

#include <iostream>
#include <stack>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
using namespace std;
int main()
{
    char a[150];
    int i,j,p,n;
    scanf("%d",&n);
    getchar();
    while(n--)
    {
        stack<char> st;
        gets(a);
        //if(a=="") {cout<<"Yes"<<endl;continue;}
        p=0,j=0;
        int count1=0,count2=0;
        for(int i=0;a[i]!='\0';i++)
        {
            if(a[i]=='[' || a[i]=='(' || a[i]=='{') {count1++;st.push(a[i]);}
            else
            {
                if(a[i]==']') if(st.top()!='[') {p=1;j=1;break;}
                else if(a[i]=='}') if(st.top()!='{') {p=1;j=1;break;}
                else if(a[i]==')') if(st.top()!='(') {p=1;j=1;break;}
                count2++;
                st.pop();
            }
        }
        //cout<<a[0]<<a[1];
        //cout<<count1<<" "<<count2;
        if(!p && !j && count1==count2) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
        fflush(stdin);
    }
    return 0;
}
Last edited by brianfry713 on Fri Jun 19, 2015 6:35 am, edited 1 time in total.
Reason: Added code blocks

Moaz
New poster
Posts: 3
Joined: Thu Apr 09, 2015 3:59 am

Re: 673 - Parentheses Balance ?WA?

Post by Moaz » Sun May 03, 2015 7:47 am

Code: Select all

#include<iostream>
#include<string>
#include<stack>
using namespace std;

int main()
{
	int n;

	cin>>n;

	getchar();
	int i=0;
	while(i<n)
	{
		stack<char>st;
		string str,news;
		getline(cin,str);
		for(int j=0;j<str.length();j++)
		{
			if(str[j]==' ')
			{
				continue;
			}
			else
			{
				news+=str[j];
			}
		}
		str=news;
		for(int j=0;j<str.length();j++)
		{	
			if(str[j]=='(')
			{
				st.push('(');
			}
			else if((str[j]==')'))
			{
				if(!st.empty()&&st.top()=='(')
				{	
					st.pop();
				}
				else
				{
					st.push(str[j]); 
				}

			}
			else if(str[j]=='[')
				st.push('[');
			else if(str[j]==']')
			{
				if(!st.empty()&&st.top()=='[')
				{	
					st.pop();
				}
				else
					st.push(str[j]);
			}


		}

		if(st.empty())
			cout<<"Yes"<<endl;
		else
			cout<<"NO"<<endl;
		i++;
	}
	return 0;
}
Last edited by brianfry713 on Fri Jun 19, 2015 6:34 am, edited 1 time in total.
Reason: Added code blocks

forhadmethun
New poster
Posts: 1
Joined: Sat Dec 28, 2013 4:21 pm

Re: 673 - Parentheses Balance

Post by forhadmethun » Fri May 15, 2015 8:46 am

Code: Select all

#include <bits/stdc++.h>
using namespace std;

int main()
{
    //cout << "Hello world!" << endl;
    freopen("in.txt","r",stdin);
    int t;
    char str[130];

    cin >> t;

    getchar();
    while(t--)
    {
        stack<char> stk;

        gets(str);
        bool isTrue = true;
        if(strlen(str) %2 ==1){
            cout << "No" << endl;
            continue;
        }
        for(int i=0;str[i];i++)
        {
            if(str[i]== '('){
                stk.push(str[i]);
                continue;}
            else if(str[i] == '['){
                    stk.push(str[i]);
                continue;
            }
            if(str[i] == ']'){
                if(stk.empty()){
                    isTrue = false;
                    break;
                }
                char ch = stk.top();
                stk.pop();
                if(ch != '['){
                    isTrue = false;
                    break;
                }
            }else if(str[i] == ')'){
                if(stk.empty()){
                    isTrue = false;
                    break;
                }
                char ch = stk.top();
                stk.pop();
                if(ch != '('){
                    isTrue = false;
                    break;
                }

            }

        }

        if(isTrue == true)cout << "Yes" << endl;
        else cout << "No" << endl;

            //cout << str << endl;



    }
    return 0;
}



///why wrong answer ................??
Last edited by brianfry713 on Fri Jun 19, 2015 6:34 am, edited 1 time in total.
Reason: Added code blocks

oja
New poster
Posts: 11
Joined: Fri Apr 24, 2015 5:34 pm

Re: 673 - Parentheses Balance

Post by oja » Fri May 15, 2015 2:39 pm

Input:

Code: Select all

1
((()
Output:

Code: Select all

No
Your code outputs "Yes".
After you process the whole string. Check if the stack is empty or not. If it's not empty then it's a "No".

Btw, couple of suggestions:

1-If you post your code, use the "Code" button at the top of the editor window. Your code may become more readable. Use
"Preview" button to view your post before you submit it.(Not that my posts are well-formatted).
2-Try not to mix c++ style (cin, cout, getline, etc) and c style (scanf, printf, fgets, etc) i/o in your c++ code. Choose c++ style or c style, but try not to use both. If you want speed for your c++ style i/o, you can use

Code: Select all

ios_base::sync_with_stdio(false);
Put it before your first use of cin or cout. And don't use "endl". You can change

Code: Select all

cout << "Yes" << endl;
to

Code: Select all

cout << "Yes\n";
endl does more work than just outputting new line. For small number of I/O, maybe there won't be any noticeable difference. But for large, your code might (or might not) finish faster.
3-You don't need to use

Code: Select all

freopen("in.txt","r",stdin);
You can just submit your code which takes input and displays output at the command line. I've tried only C++ and Java so I'm not sure if this is true with C.

Post Reply

Return to “Volume 6 (600-699)”