673 - Parentheses Balance

brianfry713 · Post by **brianfry713** » Tue Sep 04, 2012 11:53 pm

A blank line should output Yes.

sornaCse · Post by **sornaCse** » Fri Sep 07, 2012 7:19 pm

still WA!!

brianfry713 · Post by **brianfry713** » Fri Sep 07, 2012 8:07 pm

Input )( should output No.

farnaws123 · Post by **farnaws123** » Mon Dec 10, 2012 12:03 am

Code: Select all


#include<iostream>
#include<stack>
#include<vector>
#include<string>
#include<fstream>
#include<cstdlib>

/*farnaws,C++,673,08/12/2012*/

using namespace std;


string verifier(string input_line)
{
	
	stack <char> braces;
	int flag=0,count_left_first_brace=0,count_left_third_brace=0;
	for(int i=0; i<input_line.size(); i++)
	{
		if(input_line[i]=='(' || input_line[i]=='[')
		{
			braces.push(input_line[i]);
			if(input_line[i]=='(')
			{		
				count_left_first_brace++;
			}
			else if(input_line[i]=='[')
			{
				count_left_third_brace++;
			}
			
		}
		else if(input_line[i]==')' || input_line[i]==']')
		{
			if(!(braces.empty()==true))
			{
				if((input_line[i]==')' && braces.top()=='(') || (input_line[i]==']' && braces.top()=='[') )
				{
					braces.pop();	
				}
				
			}
			
			if(input_line[i]==')')
			{		
				count_left_first_brace--;
			}
			else if(input_line[i]==']')
			{
				count_left_third_brace--;
			}
		}
		else if(input_line.size()==0){
			
			flag=1;
		}
	}
	
	if((braces.empty() && !(count_left_third_brace<0 || count_left_first_brace<0)) || flag==1 )
	{
		 return "Yes";		
	}
	else
	{
		return "No";
		
	}
	
}
int main()
{
	
   ifstream file_input("C:/Users/Nawshad/Desktop/input.txt");	
   string read_file;
   vector<string> file_contents;
   int limit=0;
   if(file_input.is_open())
   {
   		while(file_input.good())
   		{
		    getline(file_input,read_file);
			file_contents.push_back(read_file); 
			limit=atoi(file_contents[0].c_str()); 	
   		}
   }
   else
   {
   		cout<<"File cant be open!"<<endl;	
   }
   ofstream file_output("C:/Users/Nawshad/Desktop/output.txt");
   if(file_output.is_open())
   {
   		for(int i=1; i<=limit; i++ )
	   	{
		   	file_output<<verifier(file_contents[i])<<endl;
		}
   		
   }
   else
   {
   		cout<<"File cant be open!"<<endl;	
   }
   	
   return 0;
	
	
}

getting WA, cant figure out why!!

farnaws123 · Post by **farnaws123** » Mon Dec 10, 2012 12:15 am

Code: Select all

#include<iostream>
#include<stack>
#include<vector>
#include<string>
#include<fstream>
#include<cstdlib>

/*farnaws,C++,673,08/12/2012*/

using namespace std;


string verifier(string input_line)
{
	
	stack <char> braces;
	int flag=0, count_left_first_brace=0,count_left_third_brace=0;
	cout<<"input size:"<<input_line.size()<<endl;
	
	//cout<<braces.empty()<<count_left_first_brace<<count_left_third_brace<<flag<<endl;
	
	for(int i=0; i<input_line.size(); i++)
	{
		
		if(input_line[i]=='(' || input_line[i]=='[')
		{
			braces.push(input_line[i]);
			if(input_line[i]=='(')
			{		
				count_left_first_brace++;
			}
			else if(input_line[i]=='[')
			{
				count_left_third_brace++;
			}
			
		}
		else if(input_line[i]==')' || input_line[i]==']')
		{
			if(!(braces.empty()==true))
			{
				if((input_line[i]==')' && braces.top()=='(') || (input_line[i]==']' && braces.top()=='[') )
				{
					braces.pop();	
				}
				
			}
			
			if(input_line[i]==')')
			{		
				count_left_first_brace--;
			}
			else if(input_line[i]==']')
			{
				count_left_third_brace--;
			}
		}
	 	
	}
	cout<<"Input line is_empty:"<<input_line.empty()<<endl;
	//cout<<braces.size()<<count_left_first_brace<<count_left_third_brace<<flag<<endl;
	
	if((braces.size()==0 && count_left_third_brace>=0 && count_left_first_brace>=0) || input_line.empty())
	{
		 return "Yes";		
	}
	else
	{	
		return "No";
	}
	
}
int main()
{
	
   ifstream file_input("C:/Users/Nawshad/Desktop/input.txt");	
   string read_file;
   vector<string> file_contents;
   int limit=0;
   int count=0;
   if(file_input.is_open())
   {
   		while(file_input.good())
   		{
		    getline(file_input,read_file);
		    cout<<read_file;
			file_contents.push_back(read_file); 
			limit=atoi(file_contents[0].c_str()); 
			count++;	
   		}
   }
   else
   {
   		cout<<"File cant be open!"<<endl;	
   }
   cout<<"count:"<<count<<endl;
   cout<<"File Content Size:"<<file_contents.size()<<endl;
   
   ofstream file_output("C:/Users/Nawshad/Desktop/output.txt");
   if(file_output.is_open())
   {
   		for(int i=0; i<limit; i++ )
	   	{
		   	file_output<<verifier(file_contents[i+1])<<endl;
		}
   		
   }
   else
   {
   		cout<<"File cant be open!"<<endl;	
   }
   	
   return 0;
	
	
}

what's wrong with it?

farnaws123 · Post by **farnaws123** » Mon Dec 10, 2012 8:12 pm

Code: Select all

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

/*farnaws,C++,673,08/12/2012*/

using namespace std;


string verifier(string input_line)
{
	
	stack <char> braces;
	int flag=0, count_left_first_brace=0,count_left_third_brace=0;
	for(int i=0; i<input_line.size(); i++)
	{
		
		if(input_line[i]=='(' || input_line[i]=='[')
		{
			braces.push(input_line[i]);
			if(input_line[i]=='(')
			{		
				count_left_first_brace++;
			}
			else if(input_line[i]=='[')
			{
				count_left_third_brace++;
			}
			
		}
		else if(input_line[i]==')' || input_line[i]==']')
		{
			if(!(braces.empty()==true))
			{
				if((input_line[i]==')' && braces.top()=='(') || (input_line[i]==']' && braces.top()=='[') )
				{
					braces.pop();	
				}
				
			}
			
			if(input_line[i]==')')
			{		
				count_left_first_brace--;
			}
			else if(input_line[i]==']')
			{
				count_left_third_brace--;
			}
		}
	 	
	}
	if((braces.size()==0 && count_left_third_brace>=0 && count_left_first_brace>=0) || input_line.empty())
	{
		 return "Yes";		
	}
	else
	{	
		return "No";
	}
	
}
int main()
{
	
   char line[128];
   int limit;
   cin>>limit;
   getchar();
   for(int i=0; i<limit; i++)
   {
		    cin.getline(line,sizeof(line));
		    string str=line;
		    cout<<verifier(str)<<endl;
   }
   
   return 0;
	
	
}

This, code is little changed, as the file operation is not allowed I have eliminated those,still getting WA.

brianfry713 · Post by **brianfry713** » Mon Dec 10, 2012 9:28 pm

Don't double post

brianfry713 · Post by **brianfry713** » Mon Dec 10, 2012 9:31 pm

Increase the line array to at least size 129.

farnaws123 · Post by **farnaws123** » Tue Dec 11, 2012 4:03 am

Worked!!!

linakhan988 · Post by **linakhan988** » Thu Dec 27, 2012 11:57 am

brianfry713 wrote:check your code with an empty string for an input, you need to read the input line by line.

its confusing..from where i could read the input line by line.

brianfry713 · Post by **brianfry713** » Sat Dec 29, 2012 11:28 am

instead of scanf("%s") use something like gets()

jalil_cse · Post by **jalil_cse** » Sat Feb 09, 2013 3:58 pm

WHY WA.........

Code: Select all

#include<stdio.h>
#include<string.h>
int main()
{ int te;

scanf("%d",&te);
getchar();
while(te--)
{
 char s[200],t;
    int i,j,l,fc=0;

gets(s);
    l=strlen(s);
    for(i=0;i<l-1;i++)
    {
        if((s[i]=='(' && s[i+1]==']')||(s[i]=='[' && s[i+1]==')'))
        {
            printf("No\n");
            fc=1;
            break;
            }
        }
        if(fc==0)
        {
    for(i=0;i<l;i++)
    {
        if(s[i]=='(')
        t=')';
        else if(s[i]=='[')
        t=']';
        for(j=i;j<l;j++)
        {
            if(s[j]==t)
            {
                s[j]='0';
                s[i]='0';
                t='\0';
                break;
                }
            }

        }
        int f=0;
        for(i=0;i<l;i++)
        {
        if(s[i]!='0')
        {
            printf("No\n");
            f=1;
            break;
            }
        }
            if(f==0)
            printf("Yes\n");
            f=0;
}
}
    return 0;
    }

brianfry713 · Post by **brianfry713** » Mon Feb 11, 2013 11:58 pm

Input:

Code: Select all

1
([[])]

AC output:

Code: Select all

No

raj · Post by **raj** » Fri Feb 15, 2013 5:45 pm

online judge says its RUN TIME ERROR .............PLEASE ANYONE HELP ME.............

import java.util.*;
public class Main{
public static void main(String [] args){
Scanner k = new Scanner(System.in);
while(true)
{
int d = k.nextInt();
k.nextLine();
for(int c = 0;c<d;c++)
{
String s = k.nextLine();
s = s.replace(" ","");
Stack<Character> a = new Stack<Character>();
int t;
for(t = 0;t<s.length();t++)
{
if(s.charAt(t)=='('||s.charAt(t)=='{'||s.charAt(t)=='[')
{
a.push(s.charAt(t));
}
else
{
if(s.charAt(t)==')')
{
if(!(a.isEmpty()))
{
if(a.pop()!='(')
{
break;
}
}
else
{
break;
}
}
else if(s.charAt(t)=='}')
{
if(!(a.isEmpty()))
{
if(a.pop()!='{')
{
break;
}
}
else
{
break;
}
}
else
{
if(!(a.isEmpty()))
{
if(a.pop()!='[')
{
break;
}
}
else
{
break;
}
}
}
}
if(a.isEmpty() && t==s.length())
{
System.out.println("Yes");
}
else
{
System.out.println("No");
}
}
}
}
}

lbv · Post by **lbv** » Fri Feb 15, 2013 6:30 pm

raj wrote:online judge says its RUN TIME ERROR .............PLEASE ANYONE HELP ME.............

Have you tried your program against an input file? Calling k.nextInt() throws a java.util.NoSuchElementException exception when the end of the input is reached.

Try removing the while(true) loop, which is not necessary.

OJ Board

673 - Parentheses Balance

Re: 673 WA!!

Re: 673 WA!!

Re: 673 WA!!

Re: 673 WA!!

673 WA, whats wrong??

Re: 673 WA, whats wrong??

Re: 673 WA!!

Re: 673 WA, whats wrong??

Re: 673 WA, whats wrong??

Re: 673 Parentheses Balance - WA ?

Re: 673 Parentheses Balance - WA ?

Re: 673 Parentheses Balance - WA ?

Re: 673 Parentheses Balance - WA ?

Re: 673 - Parentheses Balance

Re: 673 - Parentheses Balance