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 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.
brianfry713
Guru
 
Posts: 3468
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
brianfry713
Guru
 
Posts: 3468
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: 71
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: 110
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: 71
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.
brianfry713
Guru
 
Posts: 3468
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

Re: 673 - Parentheses Balance

Postby 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.
brianfry713
Guru
 
Posts: 3468
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

PreviousNext

Return to Volume VI

Who is online

Users browsing this forum: No registered users and 1 guest