673 - Parentheses Balance

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

Moderator: Board moderators

Re: 673 - Parentheses Balance

Postby ujjal.ruet » Sun Jan 23, 2011 8:52 am

I don't know where is my problem.I m getting WA in this problem. I have used stack to solve this problem.
Thanks in advanced.


EDIT: I got AC.It was a silly mistake.
ujjal.ruet
New poster
 
Posts: 15
Joined: Thu Sep 02, 2010 3:10 pm
Location: Dhaka,Bangladesh

Re: 673 - Parentheses Balance

Postby wawa » Mon Apr 04, 2011 4:05 pm

Code: Select all
#include <iostream>
#include <string>
using namespace std;
int main()
{
   int n, stk, stack[128], check, wrong;
   string str;
   cin >> n;
   cin.ignore (80, '\n');
   for (int i = 0; i < n; i++)
   {
      getline(cin, str);
      if (str == "")
         stk = 0;
      else
      {
         stk = 0;
         wrong = 0;
         for (int j = 0; j < str.size(); j++)
         {
            if (str[j] == '(')
            {
               stack[stk] = 41;
               stk++;
            }
            else if (str[j] == '[')
            {
               stack[stk] = 93;
               stk++;
            }
            else if (str[j] == ')')
            {
               if (stack[stk - 1] == 41)
                  stk = stk - 1;
               else
               {
                  wrong = 1;
                  break;
               }
            }
            else if (str[j] == ']')
            {
               if (stack[stk - 1] == 93)
                  stk = stk - 1;
               else
               {
                  wrong = 1;
                  break;
               }
            }
         }
      }
      if (stk == 0 && wrong == 0)
         cout << "Yes" << endl;
      else
         cout << "No" << endl;
   }
   return 0;
}


Why kept getting WA...?????
wawa
New poster
 
Posts: 5
Joined: Thu Dec 16, 2010 8:17 am

Re: 673 - Parentheses Balance

Postby anik.bit0104 » Sun May 01, 2011 9:26 pm

Code: Select all
#include <stdio.h>
#include <iostream>
#include <stack>
using namespace std;

int main()
{
  stack <char> bracks;
  char c;
   string s;
  long unsigned numOfTestCase;

   cin>>numOfTestCase;

  for (long unsigned i=0;i<numOfTestCase ; i++)
  {
      cin>>s;
      for (int i=0;i<s.length() ; i++)
    {
   
      if (bracks.empty())
        {
          bracks.push(s[i]);
         }


      else if (bracks.top()=='(' && s[i]==')' || bracks.top()=='[' && s[i]==']')
        {
             bracks.pop();

        }

      else if(s[i]=='(' || s[i]==')' ||  s[i]=='[' || s[i]==']')
        {
             bracks.push(s[i]);

        }
    }

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

  while(!bracks.empty()){bracks.pop();}
  }
  return 0;
}




What's wrong with my code? its correct for every input set mentioned here..
anik.bit0104
New poster
 
Posts: 6
Joined: Thu Sep 23, 2010 1:50 pm
Location: Dhaka, Bangladesh

Re: 673 - Parentheses Balance

Postby marjan » Tue Nov 01, 2011 11:57 am

I don't know how that macro exactly works,but seems it doesn't wrap stdio.h? Those using statements between _STD_BEGIN and _STD_END import those names into the std namespace. They would now be available both as size_t and std::size_t (don't ask me why they should be kept visible globally). - The C++ versions have other differences. For example, it appears that some things are macros in C libraries, which C++ redefines as normal functions. Also, <cmath> adds various overloads to functions (no overloading in C)
marjan
New poster
 
Posts: 3
Joined: Tue Nov 01, 2011 11:54 am

Re: 673 - Parentheses Balance

Postby cjahangir » Sat Dec 17, 2011 6:18 pm

#include<stdio.h>
#include<string.h>
char stack[200];
long top;
char pop();
char push(char c);
int main()
{
long i,l,n,j,k;
char c[200];
scanf("%ld",&n);

for(i=0;i<n;i++)
{
top=0;k=0;
if(i==0)
scanf("%c",&c[0]);
gets(c);
l=strlen(c);

stack[top]=c[0];

for(j=1;j<l;j++)
{
if(stack[top]=='('&&c[j]==')')
pop();
else if(stack[top]=='['&&c[j]==']')
pop();
else push(c[j]);
if(top<0&&j==l-1)
{printf("Yes\n");k=1;}
}
if(k==0)
printf("No\n");
}
return 0;
}

char push(char c)
{
top=top+1;
stack[top]=c;

}
char pop()
{
top=top-1;
}




guys .. please check ma code. i am getting rong answer.
cjahangir
New poster
 
Posts: 1
Joined: Fri Dec 09, 2011 8:27 pm

Re: 673 - Parentheses Balance

Postby brianfry713 » Tue Jan 10, 2012 1:06 am

cjahangir, check your code with an empty string for an input. Also use the code blocks when posting.
Check input and AC output for hundreds of problems on uDebug!
brianfry713
Guru
 
Posts: 3578
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 673 - Parentheses Balance

Postby wonderful008 » Thu Jul 26, 2012 4:49 pm

I have gotten WA for many times...
Can anyone help me?

#include <iostream>
using namespace std;
#define MAX 100
int Stack[MAX], top=-1;
int isEmpty();
int isFull();
int Push(char n);
char Pop();
char View();
int length(char data[]);

int main()
{
int N;
while (cin >> N) {
cin.ignore();
char data[MAX];
for (int i = 0; i < N; i++) {
cin.getline(data,MAX);
int len = length(data);
int correct = 1;
while (!isEmpty()) Pop();

for (int i = 0; i < len; i++) {
if (data[i] == '(' || data[i] == '[') {Push(data[i]);}
else if (data[i] == ')') {
if (isEmpty() || View() != '(') {correct = 0; break;}
Pop();
}
else if (data[i] == ']') {
if (isEmpty() || View() != '[') {correct = 0; break;}
Pop();
}
}

if (!isEmpty()) correct = 0;
correct == 1? cout << "Yes\n":cout << "No\n";
}
}
return 0;
}


int isEmpty()
{
if (top < 0) return 1;
else return 0;
}

int isFull()
{
if (top >= MAX-1) return 1;
else return 0;
}

int Push(char n)
{
if (isFull()) return -1;
Stack[++top] = n;
return 0;
}

char Pop()
{
if (isEmpty()) return -1;
return Stack[top--];
}

char View()
{
if (isEmpty()) return -1;
return Stack[top];
}

int length(char data[])
{
int x = 0;
for (int i = 0; data[i]!='\0'; i++)
x++;
return x;
}
wonderful008
New poster
 
Posts: 2
Joined: Thu Jul 26, 2012 4:26 pm

Re: 673 - Parentheses Balance

Postby brianfry713 » Fri Jul 27, 2012 1:30 am

Input:
Code: Select all
1
()
1
()
Output should be:
Code: Select all
Yes
Check input and AC output for hundreds of problems on uDebug!
brianfry713
Guru
 
Posts: 3578
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 673 - Parentheses Balance

Postby 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");
}
}
}
}
}
raj
Learning poster
 
Posts: 72
Joined: Fri Feb 15, 2013 5:39 pm

Re: 673 - Parentheses Balance

Postby 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.
lbv
Experienced poster
 
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 673 - Parentheses Balance

Postby raj » Fri Feb 15, 2013 6:37 pm

thanks ......... sir............ now its accepted..... :)
raj
Learning poster
 
Posts: 72
Joined: Fri Feb 15, 2013 5:39 pm

Re: 673 - Parentheses Balance

Postby Salam! » Wed Sep 11, 2013 12:06 am

Hi Guys :D
I get WA for this code on parentheses Balance.
Plz Help Me! :wink:
Code: Select all
Tnx... I Got Ac  :lol:  :lol:
}
Last edited by Salam! on Wed Sep 11, 2013 11:53 pm, edited 1 time in total.
Salam!
New poster
 
Posts: 7
Joined: Tue Sep 10, 2013 7:14 pm

Re: 673 - Parentheses Balance

Postby brianfry713 » Wed Sep 11, 2013 10:02 pm

You need to read line by line, there may be a blank line and reading a string will skip that.
Check input and AC output for hundreds of problems on uDebug!
brianfry713
Guru
 
Posts: 3578
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 673 - Parentheses Balance

Postby Salam! » Wed Sep 11, 2013 11:54 pm

brianfry713 wrote:You need to read line by line, there may be a blank line and reading a string will skip that.

Thanks Brianfry! I Got Ac!
Salam!
New poster
 
Posts: 7
Joined: Tue Sep 10, 2013 7:14 pm

Re: 673 - Parentheses Balance

Postby 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?
sahutd
New poster
 
Posts: 1
Joined: Mon Dec 09, 2013 3:01 pm

PreviousNext

Return to Volume VI

Who is online

Users browsing this forum: No registered users and 1 guest