Page 1 of 2

354 - Crazy Calculator

Posted: Wed Jan 17, 2007 4:49 pm
by rio
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.

Posted: Mon Mar 26, 2007 1:10 am
by Christian Schuster
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. :(

Posted: Mon Mar 26, 2007 2:02 am
by mf
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

Posted: Mon Mar 26, 2007 12:05 pm
by rio
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.

Posted: Mon Mar 26, 2007 1:18 pm
by mf
My program outputs 12960 for the last case.
That corresponds to (12/(3/2))*(24/(5/3))*6*5*3/2.

Posted: Mon Mar 26, 2007 4:12 pm
by rio
Thanks mf :D I got AC.
There was a flaw in my algorithm with Left associative.

Posted: Wed Apr 04, 2007 12:18 am
by LithiumDex
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

Posted: Wed Apr 04, 2007 9:01 am
by rio
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.

Posted: Wed Apr 04, 2007 4:39 pm
by LithiumDex
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


Posted: Thu Apr 05, 2007 6:11 am
by rio
Your output is same as mine.

Posted: Thu Apr 05, 2007 7:39 pm
by LithiumDex
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).

Posted: Sat May 12, 2007 8:39 pm
by ..
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

Posted: Sat May 12, 2007 8:48 pm
by mf
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

Posted: Sat May 12, 2007 9:00 pm
by ..
Thanks for help, get AC :)

Re: 354 - Crazy Calculator

Posted: Sat Mar 05, 2011 11:38 pm
by Dominik Michniewski
I passed through all datasets from this topic but I got Wrong Answer from judge.
Could anyone post more datasets ??

Best regards