Cod sursa(job #3319048)

Utilizator raul41917raul rotar raul41917 Data 30 octombrie 2025 13:10:12
Problema Evaluarea unei expresii Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.69 kb
#include <fstream>
#include <queue>
#include <stack>
#include <map>
#include <string>

#define MODULO  1000000001

using namespace std;

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

bool isDigit(char ch){
    return ch >= '0' && ch <= '9';
}

bool isOperator(char ch){
    return ch == '+' || ch == '-' || ch == '/' || ch == '*';
}

int main() {

    string expression;
    fin >> expression;

    map<char, int> precedenceRules;
    precedenceRules.insert(pair('+', 0));
    precedenceRules.insert(pair('-', 0));
    precedenceRules.insert(pair('*', 1));
    precedenceRules.insert(pair('/', 1));
    precedenceRules.insert(pair('(', -1));

    int index = 0;
    queue<int> outputQueue;
    stack<char> operatorStack;
    while(index < expression.size()){
        if(isDigit(expression.at(index))){
            int number = 0;

            while(index < expression.size() && isDigit(expression.at(index))){
                number = number * 10 + (expression.at(index) - '0');
                index++;
            }

            outputQueue.push(number);
            index--;
        }else if(isOperator(expression.at(index))){
            char currentOperator = expression.at(index);

            while(!operatorStack.empty() && precedenceRules.at(operatorStack.top()) >= precedenceRules.at(currentOperator)){
                outputQueue.push(MODULO + operatorStack.top());
                operatorStack.pop();
            }

            operatorStack.push(currentOperator);
        }else{
            if(expression.at(index) == '(')
                operatorStack.push('(');
            else{
                while(operatorStack.top() != '('){
                    outputQueue.push(MODULO+operatorStack.top());
                    operatorStack.pop();
                }

                operatorStack.pop();
            }
        }

        index++;
    }


    while(!operatorStack.empty()){
        outputQueue.push(MODULO+operatorStack.top());
        operatorStack.pop();
    }

    stack<int> result;
    while(!outputQueue.empty()){
        if(outputQueue.front() < MODULO)
            result.push(outputQueue.front());
        else{
            int currOp = outputQueue.front() - MODULO;
            int last = result.top();
            result.pop();
            int beforeLast = result.top();
            result.pop();
            if((char)currOp == '+')
                beforeLast += last;
            else if((char) currOp == '-')
                beforeLast -= last;
            else if((char)currOp == '/')
                beforeLast /= last;
            else
                beforeLast *= last;
            result.push(beforeLast);
        }

        outputQueue.pop();
    }

    fout << result.top();

    return 0;
}