172 - Calculator Language

[suman]

Tryig to solve but WA.

Code: Select all

Input
S = ((M+N)+(9*2))+(2+3)*(A+2)*(D=3)
A = B = 4
C = (D = 2)*_2
C = D = 2 * _2
F = C - D
E = D * _10
Z = 10 / 3
Y = 15 - 8 - 3
U = (((M+N)+(9*2))+(2+3)*(A+2)*(D=3))*(S = ((M+N)+(9*2))+(2+3)*(A+2)*(D=3))
#

and

Code: Select all

Output
D = 3, S = 48
A = 4, B = 4
C = -4, D = 2
D = -4
No Change
E = 40
Z = 3
Y = 10
D = 3, S = 108, U = 11664

Any hint? Please help.


- Suman

[ithamar]

I like to know about some websites that explain the way this kind of problems are solved. I already know that this is done with a Recursive descent parser but i dont understand how to do it.

Guys, You know about a good website.

I really apreciate your help. I need to learn how to solve this kind of problem and for that i need some place where the explanation about the problem its clear. Some examples wouldn't be bad.

Thanxs in advance

----------
Ithamar

[arc16]

I've solve the problem, but then when i submit it, i got RE!!!
please, if anyone can, take a look at my code, and tell me, why i got RE.

[pascal]
program uva(input,output);

{$IFNDEF ONLINE_JUDGE}
uses crt;
{$ENDIF}

const
infile = '';
outfile = '';

{$IFDEF ONLINE_JUDGE}
type tInt = integer;
{$ELSE}
type tInt = longint;
{$ENDIF}

function getch(var f : text) : char;
var ch : char;
begin
read(f,ch);
while (ch=' ') do read(f,ch);
getch:=ch;
end;

function getstr(var f : text) : string;
var
ch : char;
s : string;
begin
s:='';
ch:=getch(f); s:=s+ch;
while not eoln(f) do
begin
read(f,ch);
if (ch<>' ') then s:=s+ch;
end;
readln(f);
getstr:=s;
end;

procedure trim(var s : string);
begin
if (s='') then exit;
while (s[1]=' ') do delete(s,1,1);
while (s[length(s)]=' ') do delete(s,length(s),1);
end;

procedure replace(var src : string; torep,rep : string);
var i,j : integer;
begin
i:=pos(torep,src);
if (i>0) then
begin
if (i=1) then
src:=rep+copy(src,length(torep)+1,length(src)-length(torep))
else
src:=copy(src,1,i-1)+rep+copy(src,i+length(torep),length(src)-length(torep)-i+1);
end;
end;

const
variabel : set of char = ['A'..'Z'];
digit : set of char = ['_','0'..'9'] ;
validchar : set of char = ['_','0'..'9','A'..'Z'];

var
value,cv : array ['A'..'Z'] of tint;

function countop(s : string) : integer;
var i,j : integer;
begin
countop:=0; j:=0;
if (s='') then exit;
for i:=1 to length(s) do
if (s in ['=','+','-','/','*']) then
j:=j+1;
countop:=j;
end;

function subexpr(s:string) : string;
var
i,j,b,f : integer;
d : boolean;
done : boolean;
begin
subexpr:=s;
if (countop(s)=1) then exit; {no sub expression}
if (pos('(',s)>0) then
begin
f:=pos(')',s); {find deepest paranthesis}
b:=1;
for j:=f downto 1 do
if (s[j]='(') then
begin
b:=j;
break;
end;
subexpr:=copy(s,b,f-b+1);
exit;
end;
i:=pos('*',s); {A = 5 * 3 or }
if (i=0) then i:=pos('/',s); {A = 5 + 3 * 6 or}
if (i=0) then i:=pos('+',s); {A = B = 4}
if (i=0) then i:=pos('-',s);
if (i=0) then
begin
for j:=length(s) downto 1 do
if (s[j]='=') then
begin
i:=j;
break;
end;
end;
if (i<>0) then
begin
b:=i-1; f:=i+1;
done:=false; d:=false;
while not done do
begin
if s in validchar then
begin
d:=true;
b:=b-1;
end
else
begin
if d then begin b:=b+1; done:=true; end
else b:=b-1;
end;
if (b=1) then done:=true;
end;
done:=false; d:=false;
while not done do
begin
if s[f] in validchar then
begin
d:=true;
f:=f+1;
end
else
begin
if d then begin f:=f-1; done:=true; end
else f:=f+1;
end;
if (f=length(s)) then done:=true;
end;
subexpr:=copy(s,b,f-b+1);
end;
end;

procedure split(s : string; var opr1,opr2 : string;var oprnd : char);
var
t : string;
i : integer;
m : boolean;
begin
if (s='') then exit;
{remove paranthesis}
if (s[1]='(') then t:=copy(s,2,length(s)-1) else t:=s;
trim(t);
opr1:=''; opr2:='';
i:=1; m:=false;
while (t in variabel) or (t in digit) do
begin
if (t='_') then m:=true
else opr1:=opr1+t;
i:=i+1;
end;
if m then
if (opr1[1] in variabel) then opr1:='_'+opr1
else opr1:='-'+opr1;
while (t=' ') do i:=i+1;
oprnd:=t; i:=i+1;
while (t=' ') do i:=i+1; m:=false;
while ((t in variabel) or (t in digit)) do
begin
if (t[i]='_') then m:=true
else opr2:=opr2+t[i];
i:=i+1;
if (i>length(t)) then break;
end;
if m then
if (opr2[1] in variabel) then opr2:='_'+opr2
else opr2:='-'+opr2;
end;

function getvalue(s : string) : tint;
var
m : boolean;
t : string;
x : tint;
code : integer;
begin
t:=s;
if (t[1]='_') then
begin
m:=true;
delete(t,1,1);
end
else m:=false;
if (t[1] in variabel) then
x:=value[t[1]]
else
val(t,x,code);
if m then x:=-x;
getvalue:=x;
end;

{ B * 2 }
{ 2 * B }
{2 * (B = 7)}
function proceed(s : string) : string;
var
opr1,opr2 : string;
oprnd : char;
a,b : tint;
code : integer;
begin
proceed:='';
split(s,opr1,opr2,oprnd);
{writeln(opr1);
writeln(oprnd);
writeln(opr2);}
b:=getvalue(opr2);
if (oprnd<>'=') then a:=getvalue(opr1);
case oprnd of
'=' : value[opr1[1]]:=b;
'+' : b:=a+b;
'-' : b:=a-b;
'*' : b:=a*b;
'/' : b:=a div b;
end;
if (b<0) then
begin
str(abs(b),opr1);
opr1:='_'+opr1;
end
else
str(b,opr1);
proceed:=opr1;
end;

{calc sub operation -> (op opr op) | (var = op)}
procedure docalc(s : string);
var
t : string;
e,r : string;
c : char;
begin
if (s='') then exit;
t:=s;
move(value,cv,sizeof(value));
while (subexpr(t)<>t) do
begin
e:=subexpr(t);
r:=proceed(e);
{writeln(t,'-->',e,'=',r);}
replace(t,e,r);
{writeln(t);
readkey;}
end;
r:=proceed(t); r:='';
for c:='A' to 'Z' do
begin
if (value[c]<>cv[c]) then
begin
if (r='') then r:=c else write(output,', ');
write(output,c,' = ',value[c]:1);
end;
end;
if (r='') then writeln(output,'No Change') else writeln(output);
end;

var
s : string;

begin
{$IFNDEF ONLINE_JUDGE}
clrscr;
assign(input,infile); reset(input);
assign(output,outfile); rewrite(output);
{$ENDIF}
{---solve problem here---}
fillchar(value,sizeof(value),0);
while not eof(input) do
begin
s:=getstr(input); trim(s);
if (s<>'') then docalc(s);
end;
{---end of problem solving---}
{$IFNDEF ONLINE_JUDGE}
close(output); assign(output,''); rewrite(output);
close(input); assign(input,''); reset(input);
{$ENDIF}
end.
[/pascal]

[mag]

What about order of execution of arguments of binary operations in this problem?

Should A have value 1 or 2 in the result of executing "B=(A=1)+(A=2)" ?
And what should be the value of C after executing C=A+(A=1), where A had value 0 before?

[ileti]

it is written as right associative and support high priority to paranteses .
"B=(A=1)+(A=2)" ? A= 1 , B = 3
C=A+(A=1) A=1 , C = 2

these are my opinion.I have not solve this problem yet.Just try to build solving in mind.

[Dominik Michniewski]

Could anyone tell me what's the correct answer for this input ?

Code: Select all

A=100/_2
B=(_1+A*2)/2

I think, that answer should be:

Code: Select all

A = -50
B = 49

but I found other answer:

Code: Select all

A = -50
B = -50

Which one is correct ? Problem statement suggest, that first one is correct.

Best regards
DM

[mido]

This problem is killing me..I even found official inputs and outputs for this problem, with my solution getting(as far as I can tell from the 15000 line output file) correct answers...here's my code:

[cpp]
#include <iostream>
#include <sstream>
#include <stack>

int val[30],final[30];

using namespace std;

bool ischar(char x)
{
return (x>='A' && x<='Z');
}

struct node
{
char ch;
int val;
};

node set(char ch,int val)
{
node temp = {ch,val};
return temp;
}

void assign(int& x,char op,int&y)
{
if (op=='*') x*=y;
else if (op=='+') x +=y;
else if (op=='/') x = y/x;
else if (op=='-') x = y-x;
else x=-x;
}

bool isop(char x)
{
return (x=='*' || x=='+' || x=='-' || x=='/' || x=='_');
}

void output(bool change[])
{
int i;
bool totchange=false;
for (i=0;i<30;i++)
{
if (val!=final)
{
totchange=true;
change=true;
val=final;
}
}

if (!totchange) cout<<"No Change";
else
{
bool first=true;
int i;
for (i=0;i<30;i++)
{
if (change){
if (!first)
{
cout<<", ";
}
else first=false;
cout<<char(i+'A')<<" = "<<val;
}
}
}
cout<<endl;
}

void eval(int& sum,stack<node>& arr)
{
sum= arr.top().val;
arr.pop();
while (!arr.empty() && arr.top().ch!='(')
{
if (arr.top().ch=='=')
{
arr.pop();
final[arr.top().ch - 'A'] = sum;
arr.pop();
}
else if (isop(arr.top().ch))
{
char op = arr.top().ch;
arr.pop();
assign(sum,op,arr.top().val);
if (op!='_') arr.pop();
}
}
arr.pop();
}

void main()
{
char ch,str[500],a;
int i;
bool first=true;
for (ch='A';ch<='Z';ch++) val[ch-'A'] = 0;
cin>>ws;
stack<node> arr;
for (i=0;i<30;i++) val=final=0;

while (cin.getline(str,500,'\n') && strcmp(str,"#"))
{
bool change[30] = {false};
bool totchange=false;
stringstream ss;
ss<<str;

for (i=0;i<30;i++) final=val[i];
arr.push(set('(',-1));

while (ss>>a)
{
if (a==')')
{
int sum;
eval(sum,arr);
arr.push(set(0,sum));
}
else if (ischar(a))
{
arr.push(set(a,val[a-'A']));
}
else if (a=='(' || isop(a) || a=='=')
{
arr.push(set(a,-1));
/*
if (a=='_')
{
ss>>a;
if (isdigit(a))
{
arr.pop();
int temp;
ss.putback(a);
ss>>temp;
arr.push(set(a,-temp));
}
else ss.putback(a);
}
*/
}
else
{
int temp;
ss.putback(a);
ss>>temp;
arr.push(set(a,temp));
}
}

int sum;
eval(sum,arr);

while (!arr.empty()) arr.pop();

output(change);
cin>>ws;
}
}
[/cpp]

Thanks..

[mido]

Solved the problem...for those who want to know, the negative sign is not an operator..thus, A= _5 + 10 would give A = 5, not A = -15.

[junbin]

Your output are all correct

[Abednego]

Dominik, the correct output is the second one: -50, -50 (which is what the standard division operator in C/C++/Java will give you).

mag, the operands need to be evaluated right-to-left so in your

Code: Select all

B=(A=1)+(A=2)

the right answer is

Code: Select all

A = 1, B = 3

There are cases like this in the input. Thanks for pointing out this issue. I wouldn't have thought of it.

[Dominik Michniewski]

Finally I solved this problem - -50 and -50 is corrrect answer - I found my mistake.

Best regards
DM

[chunyi81]

My program passes all the inputs in this forum and the sample input but judge gives WA. I found a tricky input which I would like to clarify the correct output to.

Input:
A = 2
B = (A + 3) - (A = 5)
#

Should the output be:

A = 2
A = 5

OR

A = 2
A = 5, B = 3

My program gave the first output, but problem description suggests the second output.

[Krzysztof Duleba]

A = 2
A = 5

is the right answer. Bracket expressions are evaluated from left to right.

[chunyi81]

Thanks for the reply, so for the other inputs in this thread:

Input1:
B = (A = 1) + (A = 2)
#

Input2
C = A + (A = 1)
#

would give:

Output1:
A = 2, B = 3 instead of the output given in this thread: A = 1, B = 3?

Output2
A = 1, C = 2 (Same as the output given above in this thread)

I am getting a bit confused here.

[Krzysztof Duleba]

That's right. The right answer is A = 2, B = 3. The operators are right associative, so 1 - 2 - 3 = 1 - (2 - 3), but bracket expressions are evaluated from left to right, as one would expect.