Cod sursa(job #2139774)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 22 februarie 2018 19:45:06
Problema Eval Scor 10
Compilator cpp Status done
Runda Simulare 46 Marime 4.31 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream fin ("eval.in"); ofstream fout ("eval.out");

const int base = 10;
const int nmax = 26;

struct Huge {
    vector< int > x;
    int semn;
} v[nmax + 1];

int pos;
string s;

Huge neg (Huge &x) {
    Huge aux = x;
    aux.semn *= -1;
    return aux;
}

Huge operator + (Huge x, Huge y);
Huge operator - (Huge x, Huge y);

Huge operator + (Huge x, Huge y) {
    if (x.semn == y.semn) {
        Huge z = x;
        int t = 0;

        for (int i = 0; i < (int)z.x.size() || t != 0; ++ i) {
            if (i == (int)z.x.size())
                z.x.push_back( 0 );
            t += z.x[ i ];
            if (i < (int)y.x.size())
                t += y.x[ i ];

            z.x[ i ] = t % base;
            t /= base;
        }

        return z;
    } else {
        if (x.semn == 1 && y.semn == -1) {
            return x - neg( y );
        } else {
            return y - neg( x );
        }
    }
}

bool operator < (const Huge &x, const Huge &y) { /// doar pozitive
    if (x.x.size() != y.x.size()) {
        return x.x.size() < y.x.size();
    }

    int i = (int)x.x.size() - 1;
    while (i > 0 && x.x[ i ] == y.x[ i ])
        -- i;
    return x.x[ i ] < y.x[ i ];
}

Huge operator - (Huge x, Huge y) {
    if (x.semn != y.semn) {
        return x + neg( y );
    } else {
        if (x.semn == -1) {
            swap(x, y);
            x.semn *= -1, y.semn *= -1;
        }

        bool flp = 0;
        if (x < y) {
            flp = 1;
            swap(x, y);
        }

        Huge z = x;
        int t = 0;

        for (int i = 0; i < (int)y.x.size() || t != 0; ++ i) {
            if (i < (int)y.x.size()) {
                t -= y.x[ i ];
            }
            t += z.x[ i ];

            if (t < 0) {
                z.x[ i ] = t + base;
                t = -1;
            } else {
                z.x[ i ] = t;
                t = 0;
            }
        }

        while (z.x.size() && z.x.back() == 0)
            z.x.pop_back();

        if (flp == 1)
            z.semn = -1;
        return z;
    }
}

Huge operator * (Huge x, Huge y) {
    Huge z;
    z.x.resize(x.x.size() + y.x.size() - 1);

    for (int i = 0; i < (int)x.x.size(); ++ i) {
        for (int j = 0; j < (int)y.x.size(); ++ j) {
            z.x[i + j] += x.x[ i ] * y.x[ j ];
        }

        int t = 0;
        for (int j = 0; j < (int)z.x.size() || t != 0; ++ j) {
            if (j == (int)z.x.size())
                z.x.push_back( 0 );
            t += z.x[ j ];
            z.x[ j ] = t % base;
            t /= base;
        }
    }

    z.semn = x.semn * y.semn;
    return z;
}

Huge expr(), termen_ad(), termen_inmult();

Huge expr () {
    Huge ans = termen_ad();
    while (pos < (int)s.size() && (s[ pos ] == '+' || s[ pos ] == '-')) {
        if (s[ pos ] == '+') {
            ++ pos;
            ans = ans + termen_ad();
        } else {
            ++ pos;
            ans = ans - termen_ad();
        }
    }

    if (pos < (int)s.size() && s[ pos ] == ')')
        ++ pos;
    return ans;
}

Huge termen_ad () {
    Huge ans = termen_inmult();
    while (pos < (int)s.size() && s[ pos ] == '*') {
        ++ pos;
        ans = ans * termen_inmult();
    }
    return ans;
}

Huge termen_inmult () {
    if (s[ pos ] == '(') {
        ++ pos;
        return expr();
    }

    if ('a' <= s[ pos ] && s[ pos ] <= 'z') {
        ++ pos;
        return v[s[pos - 1] - 'a' + 1];
    }

    if (s[ pos ] == '+') {
        ++ pos;
        return termen_inmult();
    } else if (s[ pos ] == '-') {
        ++ pos;
        Huge aux = termen_inmult();
        return neg( aux );
    } else {
        ++ pos;
        Huge aux = termen_inmult();
        if (pos < (int)s.size() && s[ pos ] == ']') {
            ++ pos;
        }

        return aux * aux;
    }
}

int main () {
    int n;
    fin >> n;

    for (int i = 1; i <= n; ++ i) {
        fin >> s;

        v[ i ].semn = 1;
        if (s[ 0 ] == '-') {
            v[ i ].semn = -1;
        }

        for (int j = (int)s.size() - 1; j >= 0 && '0' <= s[ j ] && s[ j ] <= '9'; -- j)
            v[ i ].x.push_back(s[ j ] - '0');
    }

    fin >> s;
    Huge ans = expr();

    if (ans.semn == -1)
        fout << "-";

    for (int i = (int)ans.x.size() - 1; i >= 0; -- i) {
        fout << ans.x[ i ];
    }
    fout << "\n";

    fin.close();
    fout.close();
    return 0;
}