Cod sursa(job #1637580)

Utilizator danyvsDan Castan danyvs Data 7 martie 2016 18:07:38
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.23 kb
#include <fstream>
#include <stack>
#include <cstring>
#define NMax 100001
#define VMax 1000000000
#define plus VMax + 1
#define minus VMax + 2
#define multiply VMax + 3
#define divide VMax + 4

using namespace std;

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

char s[NMax];
int a[NMax], n;

inline int Prioritate(char c)
{
    if (c == '+' || c == '-') return 1;
    else return 2;
}

void Polish()
{
    stack < char > S;
    int i, nr;
    char c;
    for (i = 0; s[i] != 0;  ++ i)
        if (s[i] == '(')
            S.push(s[i]);
        else
            if (isdigit(s[i]))
                {
                 nr = 0;
                 while (isdigit(s[i]))
                    {
                     nr = nr * 10 + (s[i] - '0');
                     ++ i;
                    }
                 -- i;
                 a[n ++] = nr;
                }
            else
                if (s[i] == ')')
                    {
                     while (!S.empty() &&S.top() != '(')
                        {
                         c = S.top();
                         if (c == '+') a[n ++] = plus;
                         if (c == '-') a[n ++] = minus;
                         if (c == '*') a[n ++] = multiply;
                         if (c == '/') a[n ++] = divide;
                         S.pop();
                        }
                     S.pop();
                    }
                else
                    if (strchr("+-*/", s[i]) != NULL)
                         if (S.empty()) S.push(s[i]);
                         else
                            if (S.top() == '(') S.push(s[i]);
                            else
                                {
                                 while (!S.empty() && S.top() != '(' && Prioritate(S.top()) >= Prioritate(s[i]))
                                    {
                                     c = S.top();
                                     if (c == '+') a[n ++] = plus;
                                     if (c == '-') a[n ++] = minus;
                                     if (c == '*') a[n ++] = multiply;
                                     if (c == '/') a[n ++] = divide;
                                     S.pop();
                                    }
                                 S.push(s[i]);
                                }
    while (!S.empty())
        {
         c = S.top();
         if (c == '+') a[n ++] = plus;
         if (c == '-') a[n ++] = minus;
         if (c == '*') a[n ++] = multiply;
         if (c == '/') a[n ++] = divide;
         S.pop();
        }
}

void Evaluare()
{
    int i, x;
    stack < int > S;
    for (i = 0; i < n; ++ i)
        if (a[i] <= VMax) S.push(a[i]);
        else
            {
             x = S.top();
             S.pop();
             if (a[i] == VMax + 1) S.top() += x;
             if (a[i] == VMax + 2) S.top() -= x;
             if (a[i] == VMax + 3) S.top() *= x;
             if (a[i] == VMax + 4)
                if (x != 0) S.top() /= x;
                else S.top() = 0;
            }
    fout << S.top() << "\n";
}

int main()
{
    fin >> s;
    fin.close();
    Polish();
    Evaluare();
    fout.close();
    return 0;
}