727 - Equation

All about problems in Volume 7. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
medv
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

727 - Equation

Post by medv » Sun Jul 14, 2002 3:48 pm

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
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

Post by xenon » Fri Jul 19, 2002 12:05 pm

Multi input!

medv
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

727 Multi input didn't help me

Post by medv » Sat Jul 20, 2002 11:56 am

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.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

727

Post by .. » Fri Jul 26, 2002 8:25 am

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)!! :evil:

Thanks~~
Last edited by .. on Sun Apr 18, 2004 9:36 am, edited 2 times in total.

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » Fri Jul 26, 2002 12:25 pm

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
Problemsetter
Posts: 18
Joined: Wed Jan 16, 2002 2:00 am
Location: Bangladesh
Contact:

727 Equation

Post by kzaman010 » Sun Aug 04, 2002 9:22 am

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
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » Sun Aug 04, 2002 12:19 pm

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
Problemsetter
Posts: 18
Joined: Wed Jan 16, 2002 2:00 am
Location: Bangladesh
Contact:

Equation

Post by kzaman010 » Sun Aug 04, 2002 5:22 pm

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
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » Sun Aug 04, 2002 6:30 pm

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
Problemsetter
Posts: 18
Joined: Wed Jan 16, 2002 2:00 am
Location: Bangladesh
Contact:

727 Equation

Post by kzaman010 » Mon Aug 05, 2002 8:49 am

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 :cry:

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » Mon Aug 05, 2002 9:57 am

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
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

Post by Revenger » Wed Aug 14, 2002 7:05 pm

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

[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
New poster
Posts: 7
Joined: Sat May 25, 2002 8:15 am

thank you . .

Post by hlchan » Sat Dec 21, 2002 3:05 pm

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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Wed Jan 08, 2003 9:40 am

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
New poster
Posts: 21
Joined: Sun Jan 19, 2003 4:01 pm
Location: Hong Kong

727 Wrong Answer

Post by Chow Wai Chung » Sun Jan 19, 2003 4:09 pm

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]

Post Reply

Return to “Volume 7 (700-799)”