## 354 - Crazy Calculator

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

Moderator: Board moderators

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

### 354 - Crazy Calculator

Keep getting RE (signal8: floating point exception).

Maybe caused from my misinterpreting of precedence and associative.
Could someone verify my i/o test?

input:

Code: Select all

``````1

++1R
--2L
**3R
//3L
1+2+3/3
1/3-3
11*3/22+327/3/2*3-1
2*12/3/2*2*6*5*3
4+5/3*1-4*9/2*1+3*2
``````
output:

Code: Select all

``````1+2+3/3 = 4
1/3-3 = -3
11*3/22+327/3/2*3-1 = 161
2*12/3/2*2*6*5*3 = 720
4+5/3*1-4*9/2*1+3*2 = -7
``````
Thanks in advance.

Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am
I didn't yet solve this one, but IMHO two operators with the same precedence must have the same associativity. In your input, this is not the case with * and /.

Imagine the expression 2*2/3, using the precedences and associativities from your input. It could be evaluated to (2*2)/3 = 1 or to 2*(2/3) = 0. Choosing one of the evaluations would imply preferring one of the operators over the other. This is not an option, given the operators are of equal precedence.

Anyways, this doesn't quite explain your FPE.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Christian Schuster wrote:Imagine the expression 2*2/3, using the precedences and associativities from your input. It could be evaluated to (2*2)/3 = 1 or to 2*(2/3) = 0.
No, only (2*2)/3 is correct. Problem statement says that different operators of same precedence must be evaluated left to right.

rio,
My accepted program produces this output:

Code: Select all

``````1+2+3/3 = 4
1/3-3 = -3
11*3/22+327/3/2*3-1 = 162
2*12/3/2*2*6*5*3 = 720
4+5/3*1-4*9/2*1+3*2  = -7
``````

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
Thanks for your reply, Christian Schuster and mf.
I fixed the bug for the 3rd test case (which I was outputing 161), but still FPE.

Few more test cases. Verifying will help me.
INPUT

Code: Select all

``````1

++1L
--3R
**3L
//3R
10/2/2*8-2
3+8-2-1/3+1
34*33/21+3*9/11/2*4
12/3/2*24/5/3*6*5*3/2
``````
OUTPUT

Code: Select all

``````10/2/2*8-2 = 78
3+8-2-1/3+1 = 6
34*33/21+3*9/11/2*4 = 73
12/3/2*24/5/3*6*5*3/2 = 13
``````
Thanks in advance.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
My program outputs 12960 for the last case.
That corresponds to (12/(3/2))*(24/(5/3))*6*5*3/2.

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
Thanks mf I got AC.
There was a flaw in my algorithm with Left associative.

LithiumDex
New poster
Posts: 44
Joined: Tue Jun 06, 2006 6:44 pm
Location: Nova Scotia, Canada
Contact:
I can't seem to get AC on this one... My program solves all the test cases here, but gets a floating point exception after about 2 seconds.

my code:

Code: Select all

``````#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

vector<char> opmap;
vector<int> pre;
vector<int> preused;
vector<char> acc;
vector<char> acce;

int doop ( int t1, int t2, char op )
{
//cerr << acce[op] << "(" << t1 << " " << opmap[op] << " " << t2 << ") ";
switch (opmap[op])
{
case '-':
return t1 - t2;
break;
case '+':
return t1 + t2;
break;
case '*':
return t1 * t2;
break;
case '/':
return t1 / t2;
break;
}
}

int eval ( vector<int> & terms, vector<char> & ops, int ts=-1, int te=-1,
int p=9 )
{
//    cerr << endl << ts << " " << te << endl;
while (p>=0)
{
if (!preused[p])
p--;
else
{
vector<int> rem(terms.size(), 0);
int any = 0;

if (ts == -1)
{
int start = 0;
while (true)
{
//cout << ops.size() << endl;
int start;
int end;
int i;
for (i=0; i<terms.size(); i++)
if (pre[ops[i]]==p)
break;

start = i;
if (start<terms.size())
{
for (i=start; i<terms.size(); i++)
if (ops[i]!=ops[start] && ops[i]!=' ')
break;

end = i;

if ((end-start)>=1)
{
eval(terms, ops, start, end-1, p);
any = 1;
}
else
break;
}
else
break;

/*for (int i=0; i<ops.size(); i++)
{
if (ops[i]==' ')
cout << ' ';
else
cout << opmap[ops[i]];
}
cout << "|" << endl;*/
}
}

char ac = ' ';
if (ts>=0)
ac = acce[ops[ts]];

if ((ac=='L') && !any)
{
int start = 0, end = terms.size()-1;
if (ts>=0)
{
start = ts; end = te;
}
for (int i=start; i<=end; i++)
{
if (pre[ops[i]]==p && ops[i]!=' '&& !rem[i]
&& acce[ops[i]]=='L')
{
int i1=i+1;
while (i1<rem.size() && rem[i1])
i1++;
if (i1<rem.size())
{
any = 1;
terms[i] = doop(terms[i], terms[i1], ops[i]);
ops[i] = ops[i1];
rem[i1] = 1;
i--;
}
}
}
}
if ((ac=='R')&&!any)
{
int start = terms.size()-2;
int end = 0;
if (ts>=0)
{
start = te;
end = ts;
}
//                cerr << "x";
for (int i=start; i>=end; i--)
{
//                  cerr << "*" << i;
if (pre[ops[i]]==p && ops[i]!=' '&&!rem[i]
&& acce[ops[i]]=='R')
{
int i1=i+1;
while (i1<rem.size() && rem[i1])
i1++;
if (i1<rem.size())
{
any = 1;
terms[i] = doop(terms[i], terms[i1], ops[i]);
ops[i] = ops[i1];
rem[i1] = 1;
//i++;
}
}
}
//            cerr << "y";
}

vector<int> newt;
vector<char> newo;

//cerr << endl;
if (ts>=0)
{
for (int i=0; i<terms.size(); i++)
{
int ted = 0;
if (!rem[i])
{
//cerr << terms[i] << opmap[ops[i]];
newt.push_back(terms[i]);
newo.push_back(ops[i]);
if (i>=ts && i<=te)
ted++;
}
te-=ted;
}
//cerr << endl;

terms = newt;
ops = newo;
}

if (ops.size()==1)
return terms[0];

if (!any)
{
if (ts>=0)
return 0;
p--;
}
else
{
if (ts>=0)
te--;
}
}
}
}

int main ( void )
{
string line;
getline(cin, line);
istringstream iss(line);
int cases;
iss >> cases;
getline(cin, line);

for (int casen=1; casen<=cases; casen++)
{
char _opmap[256] = { 0 };
int _pre[256] = { 0 };
int _preused[50] = { 0 };
char _acc[10] = { 0 };
char _acce[256] = { 0 };
string rule;
int i;
for (i=0; i<4; i++)
{
getline(cin, rule);
_opmap[rule[1]] = rule[0];
int p = (rule[2]-'0');//*4+(3-i);
_pre[rule[1]] = p;
_preused[p]++;
_acc[p] = rule[3];
_acce[rule[1]] = rule[3];
}

opmap = vector<char>(_opmap, _opmap+256);
pre = vector<int>(_pre, _pre+256);
preused = vector<int>(_preused, _preused+50);
acc = vector<char>(_acc, _acc+10);
acce = vector<char>(_acce, _acce+256);

while (true)
{
string exp;
getline (cin, exp);
if (exp.length()==0)
break;
istringstream xin(exp);

int count = 0;

if (opmap[xin.peek()]=='-')
{
int x = -1;
while (x<0) x--;
}

vector<int> terms;
vector<char> ops;

int t; char o;

while (xin >> t)
{
cout << t;
if (xin>>o)
cout << opmap[o];
else
o = ' ';

terms.push_back(t);
ops.push_back(o);
}
cout << " = ";
cout << eval(terms, ops);
cout << endl;
}

if (casen<cases)
cout << endl;
}

return 0;
}``````
any more test cases? or any idea what I'm doing wrong?

thanks
- Chris Adams

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
I now little bit busy (and lazy) to look over your code and making io tests.
But If you post some io test, I would verify it.

LithiumDex
New poster
Posts: 44
Joined: Tue Jun 06, 2006 6:44 pm
Location: Nova Scotia, Canada
Contact:
Input:

Code: Select all

``````2

++9R
--9R
**9L
//0L
2/2+3/3+4/4+5/5
10000/2/3/4/5
100*30/2+2-5/4*10-1+99*100

++0L
--0L
**9L
//8L
5*4*3*2*1/3*2*1*2*1
1+3+10/2*800-400/2*200+6-7*3/1
``````
Output:

Code: Select all

``````2/2+3/3+4/4+5/5 = 0
10000/2/3/4/5 = 83
100*30/2+2-5/4*10-1+99*100 = 0

5*4*3*2*1/3*2*1*2*1 = 10
1+3+10/2*800-400/2*200+6-7*3/1 = -12

``````
- Chris Adams

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
Your output is same as mine.

LithiumDex
New poster
Posts: 44
Joined: Tue Jun 06, 2006 6:44 pm
Location: Nova Scotia, Canada
Contact:
Woo! AC!

I rewrote my entire eval function with 70% less code & time. (i've been working on this problem for 2.. 3? days.. wow).
- Chris Adams

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

Could any one please verify the output for me? Thanks!

Code: Select all

``````2

++0L
--0L
**9R
//9R
9/8/7*6*5*4/3/2/1
9*8*7/6*5*4/3*2*1

++1L
--3R
**3L
//3R
34*33/21+3*9/11/2*4
``````

Code: Select all

``````9/8/7*6*5*4/3/2/1 = 1080
9*8*7/6*5*4/3*2*1 = 24

34*33/21+3*9/11/2*4 = 65
``````
My signature:
• Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
My program outputs:

Code: Select all

``````9/8/7*6*5*4/3/2/1 = 1080
9*8*7/6*5*4/3*2*1 = 1120

34*33/21+3*9/11/2*4 = 73``````

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
Thanks for help, get AC
My signature:
• Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

### Re: 354 - Crazy Calculator

I passed through all datasets from this topic but I got Wrong Answer from judge.
Could anyone post more datasets ??

Best regards
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)