354 - Crazy Calculator

[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.

[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.

[mf]

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]

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]

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

[rio]

Thanks mf I got AC.
There was a flaw in my algorithm with Left associative.

[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

[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.

[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

[rio]

Your output is same as mine.

[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).

[..]

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

[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

[..]

Thanks for help, get AC

[Dominik Michniewski]

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

Best regards