673 - Parentheses Balance

[Jamsqun]

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]

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

[Jamsqun]

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

[sahutd]

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]

Either check if your stack is empty before you call pop or make pop return something if the stack is empty.

[try_tired]

#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]

Doesn't match the sample I/O.

[Ceiei]

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

[blackheartadhar]

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!

[brianfry713]

input

Code: Select all

1
(

output No

[brianfry713]

Try clearing the stack between test cases

[unreleased]

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]

Your code doesn't match sample I/O.

[nafeesdipta]

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--;
        }
    }    
}

[lighted]

Use code tags.

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..