673 - Parentheses Balance

[Jan]

Set the array size to 130.

[Samudra Banerjee]

Onek Dhonnobad, Jan. Ekhon solution Accepted hoyeche. Tobe ektu bistarito bhabe karon ta bojhate parbey ? After all, maximum string length to 128 bola chilo, tai na?

[kbr_iut]

Samudra Banerjee wrote

Onek Dhonnobad, Jan. Ekhon solution Accepted hoyeche. Tobe ektu bistarito bhabe karon ta bojhate parbey ? After all, maximum string length to 128 bola chilo, tai na?

pardon me....its a global forum.U should think about that. your language should be English.

[Samudra Banerjee]

Ya..I am really sorry....
What I wanted to say was that the max string length was given to be 128. So what was the need to set the array size to 130 ? 129 should have been enough, isn't it ?

[theharshest]

Code: Select all

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

using namespace std;

int main()
{
 int n;
 stack<char> s;
 string str;
 
 cin>>n;
 
 for(int i=0;i<n;i++)
 {
   getline(cin,str);
   
   if(str.length()==0)
   goto end;
   
   s.push(str[0]);
  
  for(int j=1;j<str.length();j++)
  {
   
   if(s.empty())
   s.push(str[j]);
   else
   {
   if((s.top()=='(' && str[j]==')') || (s.top()=='[' && str[j]==']'))
    s.pop();  
   else
    s.push(str[j]);        
   }
  }      
   
   end: 
  if(s.empty())
   cout<<"Yes"<<endl;
  else
   cout<<"No"<<endl;
  
   while(!s.empty()) 
    s.pop();
    
   // cout<<s.empty()<<endl;
    str.clear(); 
 }    
   // system("pause");
}

[bleedingeyes]

why WA
please help
here is my code

Code: Select all

#include<stdio.h>

int main()
{
	int a,i,j,flag,t;
	char arr[150];
	char ch;


	freopen("in.txt","r",stdin);

	while(scanf("%d%*c",&a)==1)
	{
		for(i=0;i<a;i++)
		{
			t=0;
			j=0;
			flag=0;
			while(1)
			{
				scanf("%c",&ch);
				if(ch=='\n')
				{
					break;
				}
				else if(ch==' ')
					continue;
				else if(ch==')')
				{
					if(!j || arr[j-1]!='(')
					{
						flag=1;
					
					}
					j--;
				}
				else if(ch==']')
				{
					if(!j || arr[j-1]!='[')
					{
						flag=1;
					
					}
					j--;
				}
				else
				{
					arr[j]=ch;
					j++;

				}
				t++;

			}
			if(flag || j ||t==0)
				printf("No\n");
			else
				printf("Yes\n");

		}


	}

	return 0;
}

[vinocit]

Hai guys. I dont reply to any post but do keep in mind that empty string has to give out "Yes" . I did this mistake and was looking into it for 3 days

[anton_indrawan]

Help me, i don't know why i got WA, i already test my code with many input...

Code: Select all

 got AC .. code removed

[mf]

Here are a couple of examples where your program goes wrong:

Code: Select all

2
[]
(([())])

Your algorithm is too complex for such a simple problem. You only need a simple stack to solve it.

[anton_indrawan]

Hai mf, thank about your information..
I got AC with 0.050 seconds using the stack (include<stack>)

Is it necessary to create own class stack ?
Which one is faster, own class stack or using the lib one ?

Thx Before.. Sorry for my language

[mf]

Is it necessary to create own class stack ?

No. And why do you even ask? If you feel like writing your own stack, just do it, it's very simple:

Code: Select all

int stk[1000], top = 0;  // the stack

push an element x:  stk[top++] = x;
popping an element: stk[--top]

You see, the ops are so simple, you don't even need a class to hold them.

[poka]

Could anyone help me, i don't know why i got WA. Here is my code in java.


import java.io.*;
import java.util.*;

public class Main
{
public static boolean oklepaji(String niz)
{
Stack<Character> s = new Stack<Character>();
for (int i = 0; i < niz.length(); i++)
{
char znak = niz.charAt(i);
if (znak == '(' || znak == '[') s.push(znak);
else if (znak == ')' && !s.empty() && s.peek() == '(') s.pop();
else if (znak == ']' && !s.empty() && s.peek() == '[') s.pop();
else return false;
}
if (!s.empty()) return false;
return true;
}

public static void main(String[] args) throws IOException
{
BufferedReader vhod = new BufferedReader(new
InputStreamReader(System.in));

int n = Integer.parseInt(vhod.readLine());
String[] tab = new String[n];
for (int i = 0; i < n; i++)
{
tab = vhod.readLine();
}
System.out.println();
for (int i = 0; i < n; i++)
{
if (oklepaji(tab)) System.out.println("Yes");
else System.out.println("No");
}
}
}

[mf]

Probably because you have an unnecessary System.out.println();

[mars kaseijin]

I went through problem description looking for sort and ordered in addition to balanced output. I found none, hence "([)]" should be Yes. Meaning the input can be jumbled as long as it balances in the end.

dont open a new thread as there is already many threads...think about that.
however ur program gives wrong output for this set of input.
input:

Code: Select all

7
([])
(([()])))
([()[]()])()
([)]
(
()(
[()

ur output is:

Code: Select all

Yes
No
Yes
Yes
No
No
No

My AC program gives:

Code: Select all

Yes
No
Yes
No
No
No
No

Hope it will help.

[anton_indrawan]

Hay mf
thx for your information, you are very experienced ... ^__^