673 - Parentheses Balance

[jan_holmes]

Yeah... using STL is possible,but when I submitted my code using STL,I got a very2 slow AC..... Maybe using Bruteforce could reduce the runtime... Hope it helps...

[Timo]

I think this problem can be solved easily if you use stack.

- scan the string from left to right
- if find '(' or '[' push them into your stack
- if find ')' or ']' and the top of the stack is not they match then break from
the looping the answer is "No". Otherwise pop from the stack
- after you finished scan the string but the stack is not empty then the answer
is "No", otherwise "Yes".

I hope you understand what I mean and can get AC.

[Roby]

Here are some input for your program:

Code: Select all

4
([])
(([()])))
([()[]()])()
[(])


The output should be:

Code: Select all

Yes
No
Yes
No

[jjtse]

I don't think '{' and '}' can be a valid input character.

INPUT:
The file contains a positive integer n and a sequence of n strings of parentheses () and [], one string a line.

[jjtse]

can there be spaces between characters in the input string?


i.e. : "([]) []"

[ayon]

no, there cant be any spaces between the characters. bcos it is said that the string consisting of parentheses () and []. surely there wont be any '{' or '}'

[Roby]

Yes, the input wouldn't have '{' and '}'. I've mistaken for read the problem description (lucky me, my code give me AC). And there also wouldn't any spaces given in the input.

Code: Select all

The file contains a positive integer n and a sequence of n strings of parentheses () and [], one string a line.

Sorry...

[Wei-Ming Chen]

What's wrong?

#include <stdio.h>
#include <string.h>
int main()
{
int a,b,e,f,g,h;

[ayon]

for input
)(
output must be "No"

[Wei-Ming Chen]

I made a very very silly mistake.....

I wanted to write "&&" , but wrote "||" instead.....

Thanks Ayon, you helped me solve this problem.

[fayyazkl]

It seems quite silly to answer a post two years old. But i thought just in case....

HERE IS THE POST

Zhao Le wrote:

I have occurred to the same question.

I can solve when using
first gets();
then atoi();

but it is C like.

I hate to both include iostream and stdio
my question is how can I turn it to C++ iostream when occurred to the multiply input.
_________________
AC makes me feels good,
But WA makes me thinks hard.

MY RESPONSE:

# include <iostream>

int n;
char str[150];

cin >> n;
cin.ignore(); // this ignores the \n at the end of line
cin >> str; // or you might use cin.getline(str,130) as an alternate

[alfreadx]

Code: Select all


#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <stack>
using namespace std;

stack<char> x;
bool judge(char *in)
{
   static int i,len;

   while(!x.empty())   x.pop();
   
   len=strlen(in);
   if(in[0] == ']' || in[0] == ')')   return 0;
   if(len % 2 != 0)   return 0;
   for(i=0;i<len;++i){
      switch(in[i]){
         case '[':
         case '(':   x.push(in[i]);   break;

         case ']':   if(x.top() == '[')   x.pop();
                  else    return 0;
                  break;
         case ')':   if(x.top() == '(')   x.pop();
                  else    return 0;
                  break;
         default : break;
      }

   }
   if(x.empty())   return 1;
   else return 0;

}
int main()
{
   int j,times;
   char in[130];

   times=atol(gets(in));
   for(j=0;j<times;++j){
      gets(in);

      if(judge(in))   cout << "Yes\n";
      else cout << "No\n";


   }


    system("pause");
    return 0;
}


i submit code , but i got RE , why ??
can you help me find bug .
thank you.

[jan_holmes]

remove "system("pause")" from your code.

[alfreadx]

oh ! thank you !!

but i got RE .

thanks again.

who can help me find bug in my code .

thank you.

[jan_holmes]

try this input :

1
(()))(

The answer should be "No".