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

Jamsqun
New poster
Posts: 2
Joined: Fri Oct 18, 2013 2:50 pm

673 What's the problem

Post by Jamsqun » Fri Oct 18, 2013 3:01 pm

Why is WA?Idon't clear about this problem.Pls give me some suggestion!

Code: Select all

#include <iostream>
#include <cstdio>
#include <stack>
#include <string.h>

using namespace std;

int main()
{

    int a;
    unsigned int i=0;
    scanf("%d",&a);
    while(a--)
    {
        string p;
        stack<char> s;
        cin>>p;
        for( i =0;i<p.length();i++)
        {
            if(p[i]=='('||p[i]=='[')
               s.push(p[i]);
            else
            {
                if(p[i]==')')
                    {
                        if(!s.empty() && s.top()=='(')
                           s.pop();    
                        else
                            s.push(p[i]);
                    }
                else
                {
                    if(!s.empty() && s.top()=='[')
                        s.pop();
                    else
                        s.push(p[i]);
                }
            }
        }
        if(!s.empty())
            cout<<"No"<<endl;
        else
            cout<<"Yes"<<endl;
    }
    return 0;
}

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

Re: 673 What's the problem

Post by brianfry713 » Fri Oct 18, 2013 7:34 pm

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
Check input and AC output for thousands of problems on uDebug!

Jamsqun
New poster
Posts: 2
Joined: Fri Oct 18, 2013 2:50 pm

Re: 673 What's the problem

Post by Jamsqun » Sat Oct 19, 2013 3:03 am

Thank you.I ingnored the blank,now it's AC.

sahutd
New poster
Posts: 1
Joined: Mon Dec 09, 2013 3:01 pm

Re: 673 - Parentheses Balance

Post by sahutd » Mon Dec 09, 2013 3:06 pm

Code: Select all

#include<cstdio>

using namespace std;
typedef struct 
{
	int top;
	char items[1000];

}stack;
bool isempty(stack *s)
{
	if(s->top==-1)
		return true;
	else
		return false;

}
char push(stack *s,int data)
{
	
	s->items[++s->top]=data;
}
char pop(stack *s)
{
		if(!isempty(s))
			return s->items[s->top--];
		

}
char stacktop(stack *s)
{
	if(!isempty(s))
		return s->items[s->top];


}
bool matchpair(char a,char b)
{
	if(a=='('&&b==')')
		return true;
	if(a=='['&&b==']')
		return true;
	if(a=='{'&&b=='}')
		return true;
	else
		return false;


}
int main()
{	
	int t;
	scanf("%d",&t);
	getchar();
	while(t--)
	{
		
		//printf("TRIAL %d\n",t);
		stack s;
		s.top=-1;
		char c;
		bool balance=true;
		
		while(scanf("%c",&c)==1)
		{
			
			//printf("%c ",c);
			if(c=='\n' || c==EOF)
				break;
			if(c=='['||c=='('||c=='{')
				push(&s,c);
			if(c==']'||c==')'||c=='}')
			{
				if(matchpair(pop(&s),c)==false)
				{
					balance=false;
					
				}
			}
		
		//getchar();
		}
		if(isempty(&s)==false)
			balance=false;
		if(balance==true)
			printf("Yes");
		else
			printf("No");
		printf("\n");
	
	}
   return 0;
}
i am using stack to solve the problem.i am also handling empty line.any pointers on where i could be going wrong?

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 09, 2013 10:55 pm

Either check if your stack is empty before you call pop or make pop return something if the stack is empty.
Check input and AC output for thousands of problems on uDebug!

try_tired
New poster
Posts: 6
Joined: Thu Jan 23, 2014 3:22 am

Re: 673 - Parentheses Balance

Post by try_tired » Thu Jan 30, 2014 10:53 am

#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

int main()
{
int i,j,k,top,n,file,ln;
char s[200],ch,st[200];
scanf("%d",&n);

top = 0;
file = 0;
for(j = 0;j<= n ;j++)
{
cin.getline(s,130,'\n');
ln = strlen(s);
for( i=0; i<ln; i++)
{
if(s[0] == ']' || s[0] == ')' )
{
file =1;
break;
}

else if(s == '(' || s == '[')
{
st[top] = s;
top++;
}

else if( (s == ']' && st[top-1] == '[' && i!=0 ) || ( s == ')' && st[top-1] == '(' && i!=0 ) )
{
top--;
}
else
{
s[top] = s;
top++;
}

}

if(j>0)
{
if(top ==0 && file == 0 || s == '\0')
printf("Yes\n");
else
printf("No\n");
}

}

return 0;
}


please tell me why i cant AC it?
where is my fault?

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 Jan 30, 2014 10:02 pm

Doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!

Ceiei
New poster
Posts: 4
Joined: Tue Mar 04, 2014 4:32 pm

Re: 673 - Parentheses Balance

Post by Ceiei » Tue Mar 04, 2014 4:37 pm

I got WA, can someone tell me what's wrong? http://ideone.com/SrdvWT

blackheartadhar
New poster
Posts: 10
Joined: Mon Nov 04, 2013 10:14 am

Re: 673 What's the problem

Post by blackheartadhar » Tue Mar 04, 2014 8:55 pm

Getting WA! It will be helpful if anyone give me some critical test case! Already tried and added a solution for the blank line case.

Code: Select all

Accepted!
Last edited by blackheartadhar on Thu Mar 06, 2014 7:45 am, edited 1 time in total.

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

Re: 673 What's the problem

Post by brianfry713 » Tue Mar 04, 2014 10:43 pm

input

Code: Select all

1
(
output No
Check input and AC output for thousands of problems on uDebug!

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

Re: 673 - Parentheses Balance

Post by brianfry713 » Tue Mar 04, 2014 10:47 pm

Try clearing the stack between test cases
Check input and AC output for thousands of problems on uDebug!

unreleased
New poster
Posts: 16
Joined: Sun Nov 10, 2013 7:41 pm

Re: 673 - Parentheses Balance

Post by unreleased » Thu Oct 09, 2014 7:59 pm

why WA??

Code: Select all

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
#include <set>
#include <stack>
#include <map>

using namespace std;
int main()
{
    string str1, str2;
    stack <char> ch;
    int a, b, c, tst,len;
    cin>>tst;
    while(tst--)
    {
        getline(cin, str1);
        len=str1.size();
        if(str1.size()<1)
        {
            cout<<"Yes\n";
            continue;
        }

        while(!ch.empty())
            ch.pop();

        for(a=0; a<len; a++)
        {
            if(str1[a]=='(' || str1[a]=='[')
            ch.push(str1[a]);


            if(str1[a]==')' ||str1[a]==']')
            {
                if(ch.empty())
                {
                    ch.push('0');
                    break;
                }
                char tmp=ch.top();

                if(tmp=='(' && str1[a]==')') ch.pop();
                if(tmp=='[' && str1[a]==']') ch.pop();

            }


        }
        if(ch.empty())cout<<"Yes\n";

        else cout<<"No\n";
    }
    return 0;
}

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

Re: 673 - Parentheses Balance

Post by lighted » Fri Oct 10, 2014 10:33 am

Your code doesn't match sample I/O.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

nafeesdipta
New poster
Posts: 1
Joined: Thu Oct 23, 2014 4:47 pm

Re: 673 - Parentheses Balance

Post by nafeesdipta » Thu Oct 23, 2014 4:52 pm

i am getting runtime error...please help

Code: Select all

package uva673;
import java.util.*;
public class Uva673 {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        
        Scanner key=new Scanner(System.in);
        int t=key.nextInt();
        Stack<Character> a;
        while(t>0)
        {
            int flag=0;            
            a = new Stack<Character>();
        String s=key.next();
            for (int i = 0; i <s.length(); i++) 
            {
            if(s.charAt(i)=='('|| s.charAt(i)=='[')
            {
            a.push(s.charAt(i));
            }
            else
            {
            if(a.empty())
            {
                System.out.println("No");
            flag++;
            break;
            }
            else if(s.charAt(i)==')'&&a.peek()=='(')
            {
            a.pop();
            }
            else if(s.charAt(i)==']'&&a.peek()=='[')
            {
            a.pop();
            }
            }
            }
        if(a.empty()&&flag!=1)
        {
            System.out.println("Yes");
        }
        else if(!a.empty())
        {
            System.out.println("No");
        }
        t--;
        }
    }    
}
Last edited by brianfry713 on Thu Oct 23, 2014 9:03 pm, edited 1 time in total.
Reason: Added code blocks

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

Re: 673 - Parentheses Balance

Post by lighted » Thu Oct 23, 2014 5:56 pm

Use code tags.
emotional blind wrote:Look at the problem description carefully
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.
There may be empty string
here is a sample input

Code: Select all

3
([)]

((([[[]]])])
and output should be

Code: Select all

no
yes
no
your code ignors the empty string..
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Post Reply

Return to “Volume 6 (600-699)”