Cod sursa(job #3370252)

Utilizator DavidLDavid Lauran DavidL Data 24 octombrie 2026 19:15:24
Problema Evaluarea unei expresii Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.64 kb
#include <fstream>
#include <iostream>
#include <stack>
#include <unordered_set>
using namespace std;
ifstream fin("evaluare.in");
ofstream fout("evaluare.out");

static constexpr char OPEN_PARENTHESIS = '(';
static constexpr char CLOSED_PARENTHESIS = ')';

enum OPERATORS {
    MULTIPLY = '*',
    DIVIDE = '/',
    ADD = '+',
    SUBTRACT = '-'
};

static const unordered_set<char> OPERATORS_SET{ MULTIPLY, DIVIDE, ADD, SUBTRACT };

inline int evaluateOperator(char operatorValue, int firstOperand, int secondOperand) {
    switch (operatorValue) {
        case MULTIPLY:
            return firstOperand * secondOperand;
        case DIVIDE:
            return firstOperand / secondOperand;
        case ADD:
            return firstOperand + secondOperand;
        default:
            return firstOperand - secondOperand;
    }
}

void evaluateTopOperation(stack<char>& operators, stack<int>& numbers, bool areStacksReversed = false) {
    // cout << "eval top operation with " << operators.size() << " operators and " << numbers.size() << " numbers\n";

    char operatorValue = operators.top();
    operators.pop();

    int secondOperand = numbers.top();
    numbers.pop();

    int firstOperand = numbers.top();
    numbers.pop();

    if (areStacksReversed) {
        swap(firstOperand, secondOperand);
    }

    numbers.push(evaluateOperator(operatorValue, firstOperand, secondOperand));
}

void actOnOperator(char operatorValue, stack<char>& operators, stack<int>& numbers) {
    operators.push(operatorValue);
}

inline bool isDigit(char character) {
    return '0' <= character && character <= '9';
}

int parseNumber(const string& expression, int firstDigitIndex) {
    int number = 0;
    for (int currentIndex = firstDigitIndex; currentIndex < (int)expression.size() && isDigit(expression[currentIndex]); currentIndex++) {
        number = number * 10 + (expression[currentIndex] - '0');
    }
    return number;
}

// Returns the index of the last character forming the number plus one.
int actOnNumber(const string& expression, int firstDigitIndex, stack<char>& operators, stack<int>& numbers) {
    int number = parseNumber(expression, firstDigitIndex);
    numbers.push(number);

    if (!operators.empty() && (operators.top() == MULTIPLY || operators.top() == DIVIDE)) {
        evaluateTopOperation(operators, numbers);
    }

    int lastDigitIndex = firstDigitIndex;
    while (lastDigitIndex + 1 < (int)expression.size() && isDigit(expression[lastDigitIndex + 1])) {
        lastDigitIndex++;
    }
    return lastDigitIndex + 1;
}

template <typename T>
stack<T> reverseStack(const stack<T>& originalStack) {
    stack<T> originalStackCopy{ originalStack };
    stack<T> reversed;
    while (!originalStackCopy.empty()) {
        reversed.push(originalStackCopy.top());
        originalStackCopy.pop();
    }
    return reversed;
}

int evaluatePlusMinusExpression(const stack<char>& operators, const stack<int>& numbers) {
    // reverse the stacks and evaluate in order of appearance
    // 4-3+1
    // before reversing :   (top)1,3,4  (top)+,-
    // after:               (top)4,3,1  (top)-,+
    // cout << "eval plus minus with " << operators.size() << " operators and " << numbers.size() << " numbers\n";
    // cout << "top of numbers: " << numbers.top() << "\n";

    stack<char> reverseOperators = reverseStack(operators);
    stack<int> reverseNumbers = reverseStack(numbers);

    while (!reverseOperators.empty()) {
        evaluateTopOperation(reverseOperators, reverseNumbers, true);
    }

    return reverseNumbers.top();
}

int evaluateExpression(const string& expression) {
    stack<char> operators;
    stack<int> numbers;

    int currentIndex = 0;
    while (currentIndex < (int)expression.size()) {
        // cout << "currIndex: " << currentIndex << "\n";
        if (OPERATORS_SET.find(expression[currentIndex]) != OPERATORS_SET.end()) {
            actOnOperator(expression[currentIndex], operators, numbers);
            currentIndex++;
        } else if (expression[currentIndex] == OPEN_PARENTHESIS) {
            operators.push(OPEN_PARENTHESIS);
            currentIndex++;
        } else if (expression[currentIndex] == CLOSED_PARENTHESIS) {
            if (operators.top() == OPEN_PARENTHESIS) {
                operators.pop();
            } else {
                evaluateTopOperation(operators, numbers);
                operators.pop();
            }
            currentIndex++;
        } else {
            currentIndex = actOnNumber(expression, currentIndex, operators, numbers);
        }
    }

    return evaluatePlusMinusExpression(operators, numbers);
}

int main() {
    string expression;
    getline(fin, expression);

    fout << evaluateExpression(expression);

    return 0;
}