Cod sursa(job #3182288)

Utilizator andreisharkVirlan Andrei Cristian andreishark Data 8 decembrie 2023 19:32:01
Problema Evaluarea unei expresii Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 5.61 kb
#include <iostream>
#include <string>
#include <fstream>
#include <stack>
#include <sstream>

int search_op_without_parantheses(const std::string& expression, int left, int right, char op1, char op2) {
    int counter = 0;

    for (int i = right; i >= left; i--) {
        if (expression[i] == ')') {
            counter++;
            continue;
        }
        else if (expression[i] == '(') {
            counter--;
            continue;
        }

        if ((expression[i] == op1 || expression[i] == op2) && counter == 0) {
            return i;
        }
    }

    return -1;
}

int get_parantheses_expression_left(const std::string& expression, int left) {
    int i = left;

    for (i = left; expression[i] != ')' && i < expression.size(); i++) {}

    if (i == expression.size()) return -1;

    return i;
}

int get_parantheses_expression_right(const std::string& expression, int right) {
    int i = right;

    for (i = right; expression[i] != '(' && i >= 0; i--) {}

    if (i == -1) return -1;

    return i;
}

bool verify_if_number(const std::string& expression, int left, int right) {
    if (expression[left] == '-') left++;

    for (int i = left; i <= right; i++) {

        if (!isalnum(expression[i])) return false;
    }

    return true;
}

int convert_to_number(const std::string& expression, int left, int right) {
    int pos = 1;
    int result = 0;

    bool ok = false;
    if (expression[left] == '-') {
        ok = true;
        left++;
    }

    for (int i = right; i >= left; i--, pos *= 10) {
        result += (expression[i] - '0') * pos;
    }

    if (ok) result *= -1;

    return result;
}

int algorithm_1(const std::string& expresion, int left, int right) {
    if (verify_if_number(expresion, left, right)) return convert_to_number(expresion, left, right);

    int result = 0;

    int pos;

    pos = search_op_without_parantheses(expresion, left, right, '+', '-');
    if (pos == -1) pos = search_op_without_parantheses(expresion, left, right, '*', '/');
    if (pos == -1) {
        result += algorithm_1(expresion, left + 1, right - 1);
        return result;
    }

    int number_left = algorithm_1(expresion, left, pos - 1);
    int number_right = algorithm_1(expresion, pos + 1, right);

    switch (expresion[pos]) {
    case '+':
        result += number_left + number_right;
        break;
    case '-':
        result += number_left - number_right;
        break;
    case '*':
        result += number_left * number_right;
        break;
    case '/':
        result += number_left / number_right;
        break;
    }

    return result;
}

int evaluate_expression(int number_1, int number_2, char op_code) {
    switch (op_code) {
    case '+':
        return number_1 + number_2;
    case '-':
        return number_1 - number_2;
    case '*':
        return number_1 * number_2;
    case '/':
        return number_1 / number_2;
    }
}

bool verify_op_code(char character) {
    if (character == '+' || character == '-' || character == '*' || character == '/' || character == '(' || character == ')') return true;

    return false;
}

int get_character_priority(char character) {
    if (character == '-' || character == '+') return 1;
    else if (character == '*' || character == '/') return 2;
    else if (character == '(' || character == ')') return 0;
}

int get_number(const std::string& expression, int& i) {
    std::stringstream buffer;

    if (expression[i] == '-') {
        buffer << '-';
        i++;
    }

    for (;!verify_op_code(expression[i]) && i < expression.size(); i++) {
        buffer << expression[i];
    }
    i--;

    int number;
    buffer >> number;
    return number;
}

void evaluate_stacks(std::stack<char>& op_codes, std::stack<int>& numbers) {
    char op_code = op_codes.top();
    op_codes.pop();

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

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

    int result = evaluate_expression(number1, number2, op_code);
    numbers.push(result);
}

int algorithm_2(const std::string& expression) {
    std::string buffer = "";
    std::stack<char> op_codes;
    std::stack<int> numbers;
    bool is_number = true;
    int parantheses_order = 0;

    for (int i = 0; i < expression.size(); i++) {
        if (expression[i] == '(') {
            op_codes.push('(');
            parantheses_order++;
            continue;
        }
        else if (expression[i] == ')') {
            parantheses_order--;
            while (op_codes.top() != '(') {
                evaluate_stacks(op_codes, numbers);
            }
            op_codes.pop();
            continue;
        }

        std::cout << expression[i];
        if (verify_op_code(expression[i])) {
            char old_op_code = '(';
            if (op_codes.size() >= 1) old_op_code = op_codes.top();
            op_codes.push(expression[i]);

            if (!(op_codes.size() >= 2) || get_character_priority(expression[i]) > get_character_priority(old_op_code)) continue;
            char temp_buffer = op_codes.top();
            op_codes.pop();

            evaluate_stacks(op_codes, numbers);

            op_codes.push(temp_buffer);
            continue;
        }

        numbers.push(get_number(expression, i));
    }

    while (!op_codes.empty()) evaluate_stacks(op_codes, numbers);

    return numbers.top();
}

int main()
{
    std::ifstream fin("evaluare.in");
    std::ofstream fout("evaluare.out");

    std::string expression;
    fin >> expression;
    fout << algorithm_2(expression);
}