Cod sursa(job #2051820)

Utilizator zdavid112zIon David-Gabriel zdavid112z Data 29 octombrie 2017 16:34:41
Problema Eval Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.2 kb
#include <bits/stdc++.h>
#define BAZA 10000

using namespace std;

struct Big
{
    int lg, neg;
    int v[300];

    void init(int nr = 0)
    {
        if(nr < 0) neg = 1, nr = abs(nr);
        else neg = 0;
        lg = 0;
        while(nr)
        {
            v[lg++] = nr % BAZA;
            nr /= BAZA;
        }
        lg = max(lg, 0);
    }

    void init(const Big& b)
    {
        neg = b.neg;
        lg = b.lg;
        memcpy(v, b.v, sizeof(v[0]) * lg);
    }

    int get(int index) const
    {
        if(index < lg) return v[index];
        return 0;
    }

    void setAddIntern(const Big& a, const Big& b)
    {
        int i, r;
        for(i = 0, r = 0; i < a.lg || i < b.lg || r; i++, r /= BAZA)
            v[i] = (r += a.get(i) + b.get(i)) % BAZA;
        lg = i;
    }

    void setSubIntern(const Big& a, const Big& b)
    {
        int i;
        v[0] = a.get(0) - b.get(0);
        for(i = 1; i < a.lg || i < b.lg; i++)
        {
            v[i] = a.get(i) - b.get(i);
            if(v[i - 1] < 0) v[i]--, v[i - 1] += BAZA;
        }
        lg = i;
        while(v[lg - 1] == 0 && lg > 1) lg--;
    }

    void setMulIntern(const Big& a, const Big& b)
    {
        Big res;
        int lgm = 0;
        memset(res.v, 0, sizeof(res.v[0]) * (a.lg + b.lg + 1));
        for(int i = 0; i < a.lg; i++)
            for(int j = 0; j < b.lg; j++)
            {
                res.v[i + j] += a.get(i) * b.get(j);
                if(res.v[i + j] != 0) lgm = max(lgm, i + j);
            }
        int i, r;
        for(i = 0, r = 0; i <= lgm || r; i++)
        {
            res.v[i] += r;
            r = res.v[i] / BAZA;
            res.v[i] %= BAZA;
        }
        res.lg = i;
        res.neg = a.neg ^ b.neg;
        init(res);
    }

    bool lessAbs(const Big& a) const
    {
        if(a.lg > lg) return true;
        if(a.lg < lg) return false;
        for(int i = lg - 1; i >= 0; i--)
        {
            if(a.v[i] > v[i]) return true;
            if(a.v[i] < v[i]) return false;
        }
        return false;
    }

    void setAdd(const Big& a, const Big& b)
    {
        if(a.neg == b.neg)
            setAddIntern(a, b), neg = a.neg;
        else
        {
            if(a.lessAbs(b))
                setSubIntern(b, a), neg = b.neg;
            else
                setSubIntern(a, b), neg = a.neg;
        }
    }

    void setSub(const Big& a, const Big& b)
    {
        if(a.neg != b.neg)
            setAddIntern(a, b), neg = a.neg;
        else
        {
            if(a.lessAbs(b))
                setSubIntern(b, a), neg = a.neg ^ 1;
            else
                setSubIntern(a, b), neg = a.neg;
        }
    }

    void setMul(const Big& a, const Big& b)
    {
        setMulIntern(a, b);
        neg = a.neg ^ b.neg;
    }

    void switchSign()
    {
        neg ^= 1;
    }

    void print()
    {
        printf("%d", v[lg - 1]);
        for(int i = lg - 2; i >= 0; i--)
            printf("%#04d", v[i]);
    }

    void scan()
    {
        static char ostr[1005];
        char* str = ostr;
        scanf("%s", str);
        if(str[0] == '-') neg = 1, str++;
        else if(str[0] == '+') neg = 0, str++;
        else neg = 0;
        int len = strlen(str);
        int cfc = 0, nrc = 0, pw = 1, indc = 0;
        for(int i = len - 1; i >= 0; i--)
        {
            nrc += (str[i] - '0') * pw;
            if(cfc == 3)
            {
                cfc = 0; pw = 1;
                v[indc++] = nrc;
                nrc = 0;
            }
            else
            {
                cfc++;
                pw *= 10;
            }
        }
        v[indc++] = nrc;
        lg = indc;
    }
};

Big var[26], resf;
char ostr[100005];
char* str;

void eval(Big& res);
void term(Big& res);
void fact(Big& res);

void eval(Big& res)
{
    res.init(0);
    term(res);
    Big aux1;
    while(*str == '+' || *str == '-')
    {
        if(*str == '+')
        {
            str++;
            term(aux1);
            res.setAdd(res, aux1);
        }
        else
        {
            str++;
            term(aux1);
            res.setSub(res, aux1);
        }
    }
}

void term(Big& res)
{
    res.init(0);
    fact(res);
    Big aux2;
    while(*str == '*')
    {
        str++;
        fact(aux2);
        res.setMul(res, aux2);
    }
}

void fact(Big& res)
{
    int neg = 0, patr = 0;
    while(*str == '+' || *str == '-' || *str == '[')
    {
        if(*str == '-' && patr == 0) neg ^= 1;
        if(*str == '[') patr++;
        str++;
    }
    if(*str == '(')
    {
        str++;
        eval(res);
        str++;
    }
    else
    {
        int index = *str - 'a';
        res.init(var[index]);
        str++;
    }
    for(int i = 0; i < patr; i++)
    {
        str++;
        res.setMul(res, res);
    }
    res.neg ^= neg;
}

int main()
{
    freopen("eval.in", "r", stdin);
    freopen("eval.out", "w", stdout);
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        var[i].scan();
    scanf("%s", ostr);
    str = ostr;
    eval(resf);
    resf.print();
    return 0;
}