Cod sursa(job #2085821)

Utilizator Teodor.mTeodor Marchitan Teodor.m Data 10 decembrie 2017 19:27:16
Problema Evaluarea unei expresii Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 2.73 kb
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef long double ld;

inline void debugMode() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    #ifndef ONLINE_JUDGE
    freopen("evaluare.in", "r", stdin);
    freopen("evaluare.out", "w", stdout);
    #endif // ONLINE_JUDGE
}
inline void PrintYes() { cout << "Yes"; }
inline void PrintNo() { cout << "No"; }

const double eps = 1e-7;
const int Nmax = 2e6 + 1;

int getValue(char *expression, int &i, int n)
{
    char value[100001] = {};
    value[0] = expression[i];
    int k = 1; ++i;

    while(i < n && isdigit(expression[i])) {
        value[k] = expression[i];
        ++i; ++k;
    }

    return atoi(value);
}

int applyOp(stack< int > &values, stack< char > &ops)
{
    int a = values.top(); values.pop();
    int b = values.top(); values.pop();
    char op = ops.top();
    ops.pop();

    switch(op)
    {
        case '+':
            return a + b;
            break;
        case '-':
            return b - a;
            break;
        case '*':
            return a * b;
        case '/':
            return b / a;
            break;
    }
}

bool hasPrecedence(char op1, char op2) /// true if op2 has higher or same precedence as op1
{
    if(op2 == '(' || op2 == ')')
        return false;
    if((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-'))
        return false;
    return true;
}

int evaluateExpression(char *expression)
{
    stack< int > values;
    stack< char > ops;

    int n = strlen(expression);
    int i;
    for(i = 0; i < n; ++i) {
        if(isdigit(expression[i])) {
            int value = getValue(expression, i, n);
            values.push(value);
            --i;
            continue;
        }

        if(expression[i] == '(') {
            ops.push(expression[i]);
            continue;
        }

        if(expression[i] == ')') {
            while(ops.top() != '(') {
                values.push(applyOp(values, ops));
            }
            ops.pop();
            continue;
        }
        /// sigur este un operator + - * /
        while(!ops.empty() && hasPrecedence(expression[i], ops.top())) {
            values.push(applyOp(values, ops));
        }
        ops.push(expression[i]);
    }

    //while((int)values.size()) cerr << values.top() << " ", values.pop();
    //cerr << endl;
    //while((int)ops.size()) cerr << ops.top() << " ", ops.pop();

    while(!ops.empty())
        values.push(applyOp(values, ops));

    return values.top();
}

int main()
{
    debugMode();

    char expression[100001];
    cin >> expression;

    cout << evaluateExpression(expression);

    return 0;
}