Cod sursa(job #1978294)

Utilizator LittleWhoFeraru Mihail LittleWho Data 7 mai 2017 12:51:11
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 4.5 kb
#include <bits/stdc++.h>

using namespace std;

#define OPERATOR 1
#define OPERAND 2

unordered_map<char, int> operators;
void init_polish_translator()
{
    operators['+'] = 1;
    operators['-'] = 1;
    operators['*'] = 2;
    operators['/'] = 2;
}

struct node_data {
    char type;
    union {
        char op;
        long long term;
    };
};

deque<node_data> to_polish(string &expression)
{
    deque<node_data> polish;
    stack<char> operators_stack;

    node_data data;
    for (int i = 0; i < expression.size(); i++) {
        //cout << "Before - OPERATOR STACK: ";
        //cout << endl;

        //cout << i << endl;
        if (expression[i] >= '0' && expression[i] <= '9') {
            //cout << "Number" << endl;
            long long number = 0;
            while (expression[i] >= '0' && expression[i] <= '9') {
                number *= 10;
                number += expression[i] - '0';
                i++;
            }
            i--;

            data.type = OPERAND;
            data.term = number;
            polish.push_back(data);
            //cout << "PUSH " << data.term << endl;
        } else if ((operators_stack.empty() || operators_stack.top() == '(' || expression[i] == '(') && expression[i] != ')') {
            //cout << "Emptry or (" << endl;
            operators_stack.push(expression[i]);
        } else if (expression[i] == ')') {
            //cout << "End )" << endl;
            while (operators_stack.top() != '(') {
                data.type = OPERATOR;
                data.op = operators_stack.top();
                polish.push_back(data);
                //cout << "PUSH " << data.op << endl;
                operators_stack.pop();
            }
            operators_stack.pop();
        } else if (operators[operators_stack.top()] == operators[expression[i]]) {
            //cout << "Equal" << endl;
            data.type = OPERATOR;
            data.op = operators_stack.top();
            polish.push_back(data);
            //cout << "PUSH " << data.op << endl;
            operators_stack.pop();
            operators_stack.push(expression[i]);
        } else if (operators[operators_stack.top()] > operators[expression[i]]) {
            //cout << "Greater" << endl;
            data.type = OPERATOR;
            data.op = operators_stack.top();
            polish.push_back(data);
            //cout << "PUSH " << data.op << endl;
            operators_stack.pop();
            i--;
        } else if (operators[operators_stack.top()] < operators[expression[i]]) {
            //cout << "Less" << endl;
            operators_stack.push(expression[i]);
        }
        //cout << "After - OPERATOR STACK: ";
        //cout << endl << endl;
    }

    while (!operators_stack.empty()) {
        data.type = OPERATOR;
        data.op = operators_stack.top();
        polish.push_back(data);
        //cout << "!PUSH " << data.op << endl;
        operators_stack.pop();
    }

    return polish;
}

long long eval_polish(deque<node_data> &polish)
{
    node_data nd;
    stack<long long> results;

    while (!polish.empty()) {
        nd = polish.front();
        polish.pop_front();

        if (nd.type == OPERATOR) {
            //if (results.empty()) throw("Results stack empty");
            long long val2 = results.top();
            results.pop();
            //if (results.empty()) throw("Results stack empty");
            long long val1 = results.top();
            results.pop();
            //cout << "EVAL " << val1 << nd.op << val2 << endl;

            switch (nd.op) {
                case '+':
                    results.push(val1 + val2);
                    break;
                case '-':
                    results.push(val1 - val2);
                    break;
                case '*':
                    results.push(val1 * val2);
                    break;
                case '/':
                    results.push(val1 / val2);
                    break;
            }
            ////cout << nd.op << endl;
        } else if (nd.type == OPERAND) {
            results.push(nd.term);
            //cout << "PUSH " << nd.term << endl;
            ////cout << nd.term << endl;
        }
    }

    //if (results.empty()) throw("Results stack empty");
    return results.top();
}

int main() {
    freopen("evaluare.in", "r", stdin);
    freopen("evaluare.out", "w", stdout);

    string expr;
    cin >> expr;

    init_polish_translator();
    deque<node_data> polish = to_polish(expr);
    //cout << "EVAL:" << endl;
    long long result = eval_polish(polish);
    cout << result << "\n";

    return 0;
}