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

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

354 - Crazy Calculator

Post by rio » Wed Jan 17, 2007 4:49 pm

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.

User avatar
Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

Post by Christian Schuster » Mon Mar 26, 2007 1:10 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:

Post by mf » Mon Mar 26, 2007 2:02 am

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

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

Post by rio » Mon Mar 26, 2007 12:05 pm

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:

Post by mf » Mon Mar 26, 2007 1:18 pm

My program outputs 12960 for the last case.
That corresponds to (12/(3/2))*(24/(5/3))*6*5*3/2.

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

Post by rio » Mon Mar 26, 2007 4:12 pm

Thanks mf :D 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:

Post by LithiumDex » Wed Apr 04, 2007 12:18 am

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

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

Post by rio » Wed Apr 04, 2007 9:01 am

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:

Post by LithiumDex » Wed Apr 04, 2007 4:39 pm

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

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

Post by rio » Thu Apr 05, 2007 6:11 am

Your output is same as mine.

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

Post by LithiumDex » Thu Apr 05, 2007 7:39 pm

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

Post by .. » Sat May 12, 2007 8:39 pm

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:

Post by mf » Sat May 12, 2007 8:48 pm

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

Post by .. » Sat May 12, 2007 9:00 pm

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

Post by Dominik Michniewski » Sat Mar 05, 2011 11:38 pm

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)

Post Reply

Return to “Volume 3 (300-399)”