727 - Equation

[medv]

Help me, why do I get Wrong answer?

(* @JUDGE_ID: 4406RA 727 PASCAL "Grammatics" *)

program Equation_727;
var
i:integer;
ch:char;

procedure a; forward;

procedure c;
begin
if (ch = '(') then
begin
readln(ch);
a;
readln(ch);
end
else
begin
write(ch);
readln(ch);
end;
end;

procedure b1;
begin
if (ch = '*') then
begin
readln(ch);
c;
write('*');
b1;
end;
if (ch = '/') then
begin
readln(ch);
c;
write('/');
b1;
end;
end;

procedure b;
begin
c; b1;
end;

procedure a1;
begin
if (ch = '+') then
begin
readln(ch);
b;
write('+');
a1;
end;
if (ch = '-') then
begin
readln(ch);
b; a1;
end;
end;

procedure a;
begin
b; a1;
end;

begin
readln(ch);
a;
writeln;
end.

[xenon]

Multi input!

[medv]

Thank you, but it didn't help me

Here is my program. I did multi input - but don't know how to read correctly - text of the problem says there only one input - one symbol in each line. Can you send me your solution?

(* @JUDGE_ID: 4406RA 727 PASCAL "Grammatics" *)

program Equation_727;
var
i:integer;
ch:string;

procedure a; forward;

procedure c;
begin
if (ch[1] = '(') then
begin
readln(ch);
a;
readln(ch);
end
else
begin
write(ch[1]);
readln(ch);
end;
end;

procedure b1;
begin
if (ch[1] = '*') then
begin
readln(ch);
c;
write('*');
b1;
end;
if (ch[1] = '/') then
begin
readln(ch);
c;
write('/');
b1;
end;
end;

procedure b;
begin
c; b1;
end;

procedure a1;
begin
if (ch[1] = '+') then
begin
readln(ch);
b;
write('+');
a1;
end;
if (ch[1] = '-') then
begin
readln(ch);
b;
write('-');
a1;
end;
end;

procedure a;
begin
b; a1;
end;

begin
readln(ch);
while (ch <> '') do
begin
a;
writeln;
end
end.

[..]

IMPORTANT(18/04/2004):
The error in judge input has been fixed.
---------------------------------------------------------------------------

After tons of WA, I got accepted on 727.
But I really confused that, why is there some input like

1(2+3)4

I have written a test program to test that there is something like this in the judge input. Can anyone tell me why is this input valid???
There is no operater between 1&2 (also 3&4)!!

Thanks~~

[Ivan Golubev]

I'm also think that judge input is incorrect in atleast one case. I suspect it happens when creating multiple input dataset and just lost one blank line, so something like this:

(1*2*3*4*5)6+2-5*9+1

can be in input. And "correct" answer for this must be:

12*3*4*5*62+59*-1+

[kzaman010]

Hello Everyone

I am getting WA for this problem. Though it can be solved in a easy
way but as a practice for PARSING, I have used parsing and Postorder
traversal. I have checked with all possible type of inputs but I may miss
something. So it would be excellent if you can provide me some
dataset. Here is my code

Code: Select all

#include <iostream.h>
#include <stdio.h>

#define MAX    100
#define E 	 	 1
#define T 		 2
#define F 		 3
#define ADD      1
#define SUB      2
#define MUL      3
#define DIV		 4

struct Node
{
	int type;
	Node *left,*right;
};
char str[MAX+1],op[]={0,43,45,42,47};

Node *createNode(int v)
{
	Node *p;
	p 	   	= new Node;
	p->type = v;
	p->left = p->right = NULL;
	return p;
}

int getPlusMinus(int start,int end,int *pos)
{
	int i,count=0;
	for(i=end;i>start;i--)
	{
		if(str[i]==')') count++;
		else if(str[i]=='(') count--;
		else if((str[i]=='+' || str[i]=='-') && !count)
			break;
	}
	if(i > start)
	{
		*pos = i;
		if(str[i]=='+')
			return ADD;
		else
			return SUB;
	}
	else
		return 0;
}

int getMulDiv(int start,int end,int *pos)
{
	int i,count=0;
	for(i=end;i>start;i--)
	{
		if(str[i]==')') count++;
		else if(str[i]=='(') count--;
		else if((str[i]=='*' || str[i]=='/') && !count)
			break;
	}
	if(i > start)
	{
		*pos = i;
		if(str[i]=='*')
			return MUL;
		else
			return DIV;
	}
	else
		return 0;
}

Node* parse(int start,int end,int type)
{
	int pos,flag;
	Node *p;

	if(type==E)
	{
		flag = getPlusMinus(start,end,&pos);
		if(!flag)
			return parse(start,end,T);
		else
		{
			p 		= createNode(flag);
			p->left = parse(start,pos-1,E);
			p->right= parse(pos+1,end,T);
			return p;
		}
	}
	else if(type==T)
	{
		flag = getMulDiv(start,end,&pos);
		if(!flag)
			return parse(start,end,F);
		else
		{
			p		= createNode(flag);
			p->left = parse(start,pos-1,T);
			p->right= parse(pos+1,end,F);
			return p;
		}
	}
	else
	{
		if(str[start]=='(')
			return parse(start+1,end-1,E);
		else
			return createNode(str[start]-'0');
	}
}

void postOrder(Node *p)
{
	if(p->left && p->right)
	{
		postOrder(p->left);
		postOrder(p->right);
		cout<<op[p->type];
		delete p;
	}
	else
	{
		cout<<p->type;
		delete p;
	}
}

int main(void)
{
	char s[80];
	int len,testCase,dataSet;
	Node *root;

	scanf("%d",&dataSet);
	getchar();
	getchar();
	for(testCase=1;testCase<=dataSet;testCase++)
	{
		for(len=0;;len++)
		{
			str[len]=getchar();
			if(str[len]=='\n' || str[len]==EOF) break;
			getchar();
		}
		str[len] = 0;
		if(len > 0)
		{
			root	 = parse(0,len-1,E);
			postOrder(root);
		}
		cout<<endl;
		if(testCase<dataSet)
			cout<<endl;
	}
	return 0;
}
[cpp][/cpp]

[Ivan Golubev]

1. Why to post this message twice? (You can always delete your post!)
2. Why you did not check this board for previous discussion about P727?

[kzaman010]

Yes I have checked the previous post about 727 but
found nothing for my solution. Its not the case whether I get this problem
AC or WA, I just want to check the mistake in my approach.

[Ivan Golubev]

Your code cannot properly handle inputs like:

1

(
1
+
2
)
3

and that's your problem. The similar input I've posted in previous thread related to P727. Another thing that such input must not be exists according to problem description... but it presents and you must deal with it.

You can run this problem and see how it gets RTE from abort().
[c]
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <ctype.h>

static char s[131072];
static char d[131072];

void checkout(void)
{
char *st;
char *dst;
int i, len;

st = s;
dst = d;
do {
while (*st <= ' ' && *st != 0) st++;
if (*st == 0) break;
*dst = *st;
dst++;
st++;
} while (1);
*dst = 0;

len = strlen(d);
for (i=0; i<len-1; i++) {
assert(!((d == ')') && isdigit(d[i+1])) );
}
}

void main(void)
{
int N;
char ss[256];

gets(ss);
N = atol(ss);
gets(ss);
while (N) {
memset(s, 0, sizeof(s));
do {
memset(ss, 0, sizeof(ss));
if (gets(ss) == NULL) break;
if (ss[0] == 0) break;
strcat(s, ss);
} while (1);

checkout();

N--;
if (N) printf("\n");
}
}
[/c]

[kzaman010]

Thanks Ivan for your help. I have never thought that such type
of data can be present. Its possible to solve a problem when Input
Output is properly defined. And there is no FIXING about this
problem. However what will be the output for (1+2)3

12+3 or 12+3* or 12+3+ or 12+3- . The output should be 12+3 but that
is not a valid postfix expression as well as the input "(1+2)3" whether
the problem statement specifies "The input will be an expression with valid syntax. "
In this sense this could be two expressions "(1+2)" "3" in a concatenated
form!!!!! And I can also expect input like :
1+23 or (2+1)(3+4)*(5+4)11

[Ivan Golubev]

Output for (1+2)3 must be 12+3. Yes, it's invalid postfix expression but it's OK because of invalid input.

And I can also expect input like :
1+23 or (2+1)(3+4)*(5+4)11

AFAIR, there cannot be such input, the only special case is "ending bracket followed by some digit". Everything else must be OK.

[Revenger]

Can anybody help me? It's seems to be all ok but I get WA

[pascal]Program p727;

Var T,i,tt : Integer;
Expp : String;
Ch : Char;

Procedure Rec(Str : String);
Var i,lev : Integer;

Procedure Evalute(Str : String);
Var i,lev : Integer;
op : Char;
S : String;
begin
op:='#';
lev:=0;
for i:=1 to length(Str) do
if lev=0 then begin
if Str in ['0'..'9'] then begin
Write(Str);
if op in ['*','/'] then Write(op);
end else
if Str in ['*','/'] then op:=Str else
if Str='(' then begin
lev:=1;
S:='';
end;
end else begin
if Str='(' then lev:=lev+1 else
if Str=')' then begin
lev:=lev-1;
if lev=0 then Rec(S);
end;
S:=S+Str;
end;
end;

begin
lev:=0;
for i:=length(Str) downto 2 do
if Str=')' then lev:=lev+1 else
if Str='(' then lev:=lev-1 else
if ((Str[i]='-') or (Str[i]='+')) and (lev=0) then begin
Rec(Copy(Str,1,i-1));
Evalute(Copy(Str,i+1,length(Str)-i));
Write(Str[i]);
Exit;
end;
Evalute(Str);
end;

Procedure StrConcat(Var S : String; Var Ch : Char);
begin
S:=S+Ch;
end;

begin
Readln(T);
for tt:=1 to T do begin
Readln;
Expp:='';
While (Not Eoln) And (Not Eof) do begin
Read(Ch);
While Ch=' ' do Read(Ch);
Readln;
StrConcat(Expp,Ch);
end;
Rec(Expp);
Writeln;
Writeln;
end;
end.[/pascal]

[hlchan]

Thank you . . for the hint....

I am really disappointed by the test data, and i wonder how can the first person get this problem accepted.

[Dominik Michniewski]

Sorry for placing my code here, but I don't know what could be wrong with this code .... I handle, perhaps properly, special inputs like (1+2)3, but I got WA every time, when I send it to OJ. It's simple parser - maybe I made some stupid mistake ?
Maybe anyone know any input, on which my program fails ?
Please help ....

Dominik Michniewski

My code is:

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

typedef struct _node { char value; struct _node *left,*right; } NODE;

char *s;

NODE *E(void);

NODE *D(void)
{
	NODE *t = (NODE *)calloc(1,sizeof(NODE));

	if(*s == 0) return NULL;
	t->value = *s;
	t->left = t->right = NULL;
	s++;
	return t;
}

NODE *F(void)
{
	NODE *t;
	char ch;

	if(*s == '(')
	{
		s++;
		t = E();
		if(*s == ')') s++;
	}
	else
		t = D();
	return t;
}

NODE *T1(NODE *x)
{
	NODE *t = NULL,*p;

	if((*s == '/') || (*s == '*'))
	{
		t = (NODE *)calloc(1,sizeof(NODE));
		t->value = *s;
		s++;
		t->left = NULL;
		p = F();
		t->left = x;
		t->right = p;
		p = T1(t);
		if(p != NULL) t = p;
	}
	return t;
}

NODE *T(void)
{
	NODE *t,*p;

	p = F();
	t = T1(p);
	if(t == NULL) t = p;
	return t;
}

NODE *E1(NODE *x)
{
	NODE *t = NULL,*p;

	if((*s == '-') || (*s == '+'))
	{
		t = (NODE *)calloc(1,sizeof(NODE));
		t->value = *s;
		s++;
		t->left = NULL;
		p = T();
		t->left = x;
		t->right = p;
		p = E1(t);
		if(p != NULL) t = p;
	}
	return t;
}

NODE *E(void)
{
	NODE *t,*p;

	p = T();
	t = E1(p);
	if(t == NULL) t = p;
	return t;
}

int ReadExpression(char *s)
{
	char line[200],*t,f = 1;

	while(gets(line) != NULL)
	{
		if(line[0] == 0) break;
		f = 0;
		t = line;
		while(isspace(*t)) t++;
		*s = *t;
		s++;
	}
	if(f) return 0;
	*s = 0;
	return 1;
}

void Print(NODE *r)
{
	if(r == NULL) return;
	Print(r->left);
	Print(r->right);
	printf("%c",r->value);
	free(r);
}

int main(void)
{
	int n,N;
	char line[200];
	NODE *tree;

	scanf("%d",&N);
	gets(line);
	gets(line);
	for(n=0;n<N;n++)
	{
		if(ReadExpression(line) == 0) break;
		s = line;
		while(*s)
		{
			tree = E();
			Print(tree);
		}
		printf("\n");
		if(n < N-1) printf("\n");
	}
	return 0;
}

[/code]

[Chow Wai Chung]

I had try many dataset to test my program, and it seems OK, but i reveive WA from the judge!!!
I also had read the message here about P727, it seems the test data of this program have something wrong. But i still don't know what wrongs with my program?
Thank you

[c]
#include <stdio.h>
#include <ctype.h>

int main()
{
int pointer=0;
char stack[60],input;
while((input=getchar())!=EOF)
{
if(isdigit(input))
printf("%c",input);
else if(input=='(')
stack[pointer++]=input;
else if(input=='*'||input=='/')
while(1)
if(pointer==0 || stack[pointer-1]=='+' || stack[pointer-1]=='-' || stack[pointer-1]=='(')
{
stack[pointer++]=input;
break;
}
else
printf("%c",stack[--pointer]);
else if(input=='+' || input=='-')
while(1)
if(pointer==0 || stack[pointer-1]=='(')
{
stack[pointer++]=input;
break;
}
else
printf("%c",stack[--pointer]);
else if(input==')')
while(stack[--pointer]!='(')
printf("%c",stack[pointer]);
}
while(pointer>0)
{
if(stack[--pointer]=='(')
continue;
printf("%c",stack[pointer]);
}
printf("\n");
return 0;
}
[/c]