673 - Parentheses Balance
Moderator: Board moderators
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 673 why RE???
Your program can assume that the maximum string length is 128.
A string of this type is said to be correct if it is the empty string.
A string of this type is said to be correct if it is the empty string.
Check input and AC output for thousands of problems on uDebug!
-
- Learning poster
- Posts: 87
- Joined: Thu Dec 15, 2011 3:08 pm
- Location: University of Rajshahi,Bangladesh
Why WA !!!!!!!
Edited but still WA!!!
[/color]
Code: Select all
#include<stdio.h>
int main()
{
int I,K,L,Flag,M,N,Test;
char Stack[200],C;
while(scanf("%d",&Test)==1)
{
//getchar();
for(;Test>0;Test--)
{
I=-1;
Flag=0;
scanf("\n");
while(scanf("%c",&C)&&C!='\n')
{
if(Flag==0)
{
if(C=='('||C=='[') Stack[++I]=C;
else if(C==')')
{
if(I<0) Flag=5;
else if(Stack[I]=='(') --I;
else Flag=5;
}
else if(C==']')
{
if(I<0) Flag=5;
else if(Stack[I]=='[') --I;
else Flag=5;
}
}
}
if(Flag==0) printf("Yes\n");
else printf("No\n");
}
}
return 0;
}
Last edited by mahade hasan on Tue Jun 05, 2012 7:35 pm, edited 1 time in total.
we r surrounded by happiness
need eyes to feel it!
need eyes to feel it!
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 673 why RE???
Don't use getchar() and assume that it will read a newline. That won't work if there are trailing spaces.
Check input and AC output for thousands of problems on uDebug!
-
- New poster
- Posts: 2
- Joined: Thu Jul 26, 2012 4:26 pm
Re: 673 - Parentheses Balance
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 == '(' || data == '[') {Push(data);}
else if (data == ')') {
if (isEmpty() || View() != '(') {correct = 0; break;}
Pop();
}
else if (data == ']') {
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!='\0'; i++)
x++;
return x;
}
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 == '(' || data == '[') {Push(data);}
else if (data == ')') {
if (isEmpty() || View() != '(') {correct = 0; break;}
Pop();
}
else if (data == ']') {
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!='\0'; i++)
x++;
return x;
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 673 - Parentheses Balance
Input:Output should be:
Code: Select all
1
()
1
()
Code: Select all
Yes
Check input and AC output for thousands of problems on uDebug!
673 Parentheses Balance - WA ?
I don't know why, got lots of test cases passed:
Code: Select all
Remove after AC
Last edited by c0debreak on Sun Aug 19, 2012 6:27 am, edited 2 times in total.
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 673 Parentheses Balance - WA ?
check your code with an empty string for an input, you need to read the input line by line.
Check input and AC output for thousands of problems on uDebug!
Re: 673 Parentheses Balance - WA ?
I think if the whole line is empty, cin will not write to the string, am I wrong ?
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 673 Parentheses Balance - WA ?
Yes that could be your problem. Try using getline(cin,str);
Check input and AC output for thousands of problems on uDebug!
Re: 673 Parentheses Balance - WA ?
If i switch to getline and check for empty strings;
I got a TLE, guess it's waiting for input maybe
Code: Select all
getline (cin, str);
if (str.empty()) { ++N; continue; }
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 673 Parentheses Balance - WA ?
Print Yes on an empty string and count it as a line. Next time post your complete updated code.
Check input and AC output for thousands of problems on uDebug!
Re: 673 Parentheses Balance - WA ?
Thanks, I've updated code to handle empty string now, but still WA
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 673 Parentheses Balance - WA ?
Try input:
((
((
Check input and AC output for thousands of problems on uDebug!
Re: 673 Parentheses Balance - WA ?
Got ACC, thanks