## 727 - Equation

Moderator: Board moderators

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

### 727 - Equation

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
a;
end
else
begin
write(ch);
end;
end;

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

procedure b;
begin
c; b1;
end;

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

procedure a;
begin
b; a1;
end;

begin
a;
writeln;
end.

xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland
Multi input!

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

### 727 Multi input didn't help me

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
a;
end
else
begin
write(ch[1]);
end;
end;

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

procedure b;
begin
c; b1;
end;

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

procedure a;
begin
b; a1;
end;

begin
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

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~~
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
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
Contact:

### 727 Equation

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 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]=='+')
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
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
Contact:

### Equation

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

### 727 Equation

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
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
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia
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
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
for tt:=1 to T do begin
Expp:='';
While (Not Eoln) And (Not Eof) do begin
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 . .

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

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;
}

{
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++)
{
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

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]