Cod sursa(job #3370333)

Utilizator DavidLDavid Lauran DavidL Data 25 octombrie 2026 15:41:54
Problema Evaluarea unei expresii Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.86 kb
#include <fstream>
#include <iostream>
#include <stack>
#include <unordered_set>
#include <vector>
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 = '-'
};

enum PostfixElementType {
    NUMBER_TYPE,
    OPERATOR_TYPE
};

struct PostfixElement {
    PostfixElementType elementType;
    int value;
};

struct PostfixNotation {
    vector<PostfixElement> elements;
};

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<int>& numbers, char operatorValue) {
    int secondOperand = numbers.top();
    numbers.pop();

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

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


// Higher value means a higher precedence (evaluated before those with lower precedence)
inline int getPrecedence(char operatorValue) {
    if (operatorValue == MULTIPLY || operatorValue == DIVIDE) {
        return 2;
    } else if (operatorValue == ADD || operatorValue == SUBTRACT) {
        return 1;
    }
    return 0;
}

void actOnOperator(char operatorValue, stack<char>& operators, PostfixNotation& postfixNotation) {
    while (!operators.empty() && getPrecedence(operators.top()) >= getPrecedence(operatorValue)) {
        postfixNotation.elements.push_back(PostfixElement{OPERATOR_TYPE, operators.top()});
        operators.pop();
    }
    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, PostfixNotation& postfixNotation) {
    int number = parseNumber(expression, firstDigitIndex);
    postfixNotation.elements.push_back(PostfixElement{NUMBER_TYPE, number});

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

PostfixNotation getPostfixNotation(const string& expression) {
    stack<char> operators;
    PostfixNotation postfixNotation;

    int currentIndex = 0;
    while (currentIndex < (int)expression.size()) {
        if (OPERATORS_SET.find(expression[currentIndex]) != OPERATORS_SET.end()) {
            actOnOperator(expression[currentIndex], operators, postfixNotation);
            currentIndex++;
        } else if (expression[currentIndex] == OPEN_PARENTHESIS) {
            operators.push(OPEN_PARENTHESIS);
            currentIndex++;
        } else if (expression[currentIndex] == CLOSED_PARENTHESIS) {
            while (operators.top() != OPEN_PARENTHESIS) {
                postfixNotation.elements.push_back(PostfixElement{OPERATOR_TYPE, operators.top()});
                operators.pop();
            }
            operators.pop();

            currentIndex++;
        } else {
            currentIndex = actOnNumber(expression, currentIndex, operators, postfixNotation);
        }
    }

    while (!operators.empty()) {
        postfixNotation.elements.push_back(PostfixElement{OPERATOR_TYPE, operators.top()});
        operators.pop();
    }

    return postfixNotation;
}

int evaluatePostfixExpression(PostfixNotation& postfixExpression) {
    stack<int> numbers;

    for (const auto& element : postfixExpression.elements) {
        if (element.elementType == NUMBER_TYPE) {
            numbers.push(element.value);
        } else {
            evaluateTopOperation(numbers, element.value);
        }
    }

    return numbers.top();
}

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

    PostfixNotation postfixNotation = getPostfixNotation(expression);

    // for (auto& element : postfixNotation.elements) {
    //     if (element.elementType == NUMBER_TYPE) {
    //         cout << element.value << " ";
    //     } else {
    //         cout << (char)element.value << " ";
    //     }
    // }

    fout << evaluatePostfixExpression(postfixNotation);

    return 0;
}