172 - Calculator Language

chunyi81 · Post by **chunyi81** » Tue Jul 20, 2004 12:27 pm

Thanks very much for your patience.

chunyi81 · Post by **chunyi81** » Wed Jul 21, 2004 3:31 pm

I found an AC program online and tested the inputs in this thread.

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

gives the output

A = 1, B = 3

and therefore,

the input

A = 2
B = (A + 3) - (A = 5)

gives

A = 2
A = 5, B = 3
Brackets are evaluated from right to left, right associativity, just like for the operators.

Krzysztof Duleba · Post by **Krzysztof Duleba** » Wed Jul 21, 2004 8:07 pm

You know, I got AC too. I wrote a simple single-character parser, parsing characters from left to right. In my parser a closing bracket meant that current value should be returned level up so that it will be used as a right side of an operator. An opening bracket meant that the parser should go level down. Brackets had no other special meaning. I could even read the input character by character with no harm to result (but with harm to efficiency of course).

Tell me if you ever get AC parsing brackets from right to left - what will mean that there are no such cases like aforementioned in the input.

chunyi81 · Post by **chunyi81** » Thu Jul 22, 2004 10:46 am

I am parsing the input from left to right as well, and I am still getting WA, and I think I found the problem.

Input:
Q=D=L=Z=_9+_31-S=13-H=V=((W=N=T=_28/6721)+45+78 )-68/2197
#

Correct Output:
D = 132, H = 123, L = 132, Q = 132, S = -110, V = 123, Z = 132

My program output:
D = 70, H = 123, L = 70, Q = 70, S = -110, V = 123, Z = 70

It seems that _10+5 = -15 instead of 5, although I found in another thread that _10+5 = 5. The above input is extracted from an official input file I found on the Web.

Krzysztof Duleba · Post by **Krzysztof Duleba** » Thu Jul 22, 2004 11:01 am

My program also returns

D = 70, H = 123, L = 70, Q = 70, S = -110, V = 123, Z = 70

For input

A=_10+5

I get

A = -5

There must me something else that you messed up, since you have right answers for those cases (right meaning similar to mine) and still get WA. I just wonder what you mean by "official input file" as it sounds very funny.

chunyi81 · Post by **chunyi81** » Thu Jul 22, 2004 11:23 am

Krzysztof Duleba wrote:My program also returns
D = 70, H = 123, L = 70, Q = 70, S = -110, V = 123, Z = 70
For input
A=_10+5
I get
A = -5
There must me something else that you messed up, since you have right answers for those cases (right meaning similar to mine) and still get WA. I just wonder what you mean by "official input file" as it sounds very funny.

Sorry, I mean I actually found the input file for the original problem(not the one in the OJ), but the original contest problem. The original problem must have been a little different from the one in the OJ. There must be something else I messed up.

I have checked through my code again and again but I cannot find the error.

Krzysztof Duleba · Post by **Krzysztof Duleba** » Thu Jul 22, 2004 2:04 pm

So you should send your code here - that's the only way we can make any progress.

chunyi81 · Post by **chunyi81** » Thu Jul 22, 2004 3:21 pm

Here is my WA code. If you can spot any bug, do tell. Thanks.

[c]
Code renoved. Problem resolved.
[/c]

It looks a bit complex but the algorithm used is as follows: for each line in the input, using a stack to hold variables and numbers(the operands) and another stack to hold the operators. The parse function is recursive, for each '(' encountered, the parse function is called again and when a matching ')' is encountered, the function evaluates whatever was in the brackets and returns the index i of the ')' character, such that when the for loop increments this index i, the index i will then point to the character after the ')'.

Krzysztof Duleba · Post by **Krzysztof Duleba** » Thu Jul 22, 2004 5:40 pm

What compiler do you use? I tried your code with gcc 2.95 (the same version as OJ is using) and for the input that we were talking about it produced the following output:

Input:
A=_10+5
#

Output:
A = -445

Input:
Q=D=L=Z=_9+_31-S=13-H=V=((W=N=T=_28/6721)+45+78 )-68/2197
#

Output:
D = 26, H = 1091, L = 26, Q = 26, S = -594, V = 1091, Z = 26

It even works bad for the sample input:

Input:
A = B = 4
C = (D = 2)*_2
C = D = 2 * _2
F = C - D
E = D * _10
Z = 10 / 3
#

Output:
A = 48, B = 48
C = -2116, D = 46
D = -2116
No Change
E = 1045304
Z = 10

chunyi81 · Post by **chunyi81** » Fri Jul 23, 2004 5:24 am

I'm using gcc 2.95 in Unix. That's strange, it should not produce the output you have given. Let me check again. Could you try with the code I've changed above? It seems that the forum converted the "8 )" characters to a smiley -

. Try and see if it still gives the output you have posted. I have also had problems with problem 139. My code for problem 139 is somewhere further down in this forum. I have also shifted the evaluation of the expression into a new function, but still getting WA.

Krzysztof Duleba · Post by **Krzysztof Duleba** » Fri Jul 23, 2004 2:55 pm

I've noticed the smiley, but changed it simply to ')'. Adding '8' makes your code work fine.

BTW - I've just spotted a bug in my code. It produced wrong answer for the sample input! It couldn't handle the case when the last character in a line was a letter. However, OJ accepted it, and accepted also fixed version

I see no obvious mistake in your code, it passed all my tests. There must be something really small and all I can tell you is to make some constraints that have to be obeyed. Then look at your code line by line and make sure everything is ok.

chunyi81 · Post by **chunyi81** » Fri Jul 23, 2004 3:35 pm

I found an AC program from a Japanese website on the Web. I compared the output to the following input for that program and my program. The AC program processes brackets from right to left.

Input:
A=_(1)
#

AC program output:
A = -1

My program output:
A = 1

This is interesting. Are there such inputs in the judge? If so, then I think I may have found the bug in my code. It cannot handle cases like the one shown.

Krzysztof Duleba · Post by **Krzysztof Duleba** » Fri Jul 23, 2004 3:55 pm

I believe that -1 is the right answer and that's what my code returns.

chunyi81 · Post by **chunyi81** » Sat Jul 24, 2004 6:14 am

I corrected that bug, but still get WA. Now I finally caught that bug. It was the eval() function where I check whether the value of a variable is changed after evaluating an expression.

Input:
A = B = 4
B=B-6+B=100
C = (D = 2) * _2
C = D = 2 * _2
E = D * _10
F = 15 - 8 - 3
F = 15 - 8 + _3
F=1+F=F-1
A=((3))
Z=Y=X=A=B=C=1+D=E=F=G=2-H=K=J=I=L=M=O=N=P=Q=R=S=T=V=U=W=3
A=100/2
A=100/_2
B=(_1+A*2)/2
B=(1+A*_2)/2
A=(((1-2)*3)+4)
A=((1-(2*3))+4)
A=((1-2)*(3+4))
A=(1-(2*(3+4)))
A=1+2+1+1+1+1+1+1+1+1+1+1+1+1+1+11+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+3
#

Correct Output:
A = 4, B = 4
B = -6
C = -4, D = 2
D = -4
E = 40
F = 10
No Change
No Change
A = 3
A = 0, B = 0, C = 0, D = -1, E = -1, F = -1, G = -1, H = 3, I = 3, J = 3, K = 3, L = 3, M = 3, N = 3, O = 3, P = 3, Q = 3, R = 3, S = 3, T = 3, U = 3, V = 3, W = 3
A = 50
A = -50
B = -50
B = 50
A = 1
A = -1
A = -7
A = -13
A = 62

My program output:
A = 4, B = 4
B = -6
C = -4, D = 2
D = -4
E = 40
F = 10
No Change
F = 10 (Wrong Answer Here!

)
A = 3
A = 0, B = 0, C = 0, D = -1, E = -1, F = -1, G = -1, H = 3, I = 3, J = 3, K = 3, L = 3, M = 3, N = 3, O = 3, P = 3, Q = 3, R = 3, S = 3, T = 3, U = 3, V = 3, W = 3
A = 50
A = -50
B = -50
B = 50
A = 1
A = -1
A = -7
A = -13
A = 62

Now I know I must check the final value of a variable after an expression is evaluated with its value before the expression is evaluated. This means I cannot check the value of a variable during evaluation.

Krzysztof Duleba · Post by **Krzysztof Duleba** » Sat Jul 24, 2004 6:27 pm

I agree with the output. Did you finally get AC?