Cod sursa(job #2274719)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 2 noiembrie 2018 13:06:42
Problema Evaluarea unei expresii Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.46 kb
#include <iostream>
#include <cctype>
#include <stack>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <fstream>

class Expression {
private:
    std::string infixExpression;
    std::unordered_map<std::string, int (*)(int, int)> operationFunctions;
    std::unordered_map<std::string, int> operationPrecedence;

    bool isOperator(char);
    bool isOperand(const std::string&);
    int getPrecedence(char);
    std::string removeWhitespaces(const std::string&);


    std::vector<std::string> createPostfixExpression();
    int evaluatePostfixExpression(const std::vector<std::string>&);
    int computeOperation(const std::string&, int, int);

public:
    Expression(const std::string&);

    void addOperation(const std::string&, int, int(*)(int, int));
    int evaluate();
};
int main() {
    std::ifstream in("../evaluare.in");
    std::ofstream out("../evaluare.out");

    std::string infixExpression;
    std::getline(in, infixExpression);

    Expression expression(infixExpression);

    expression.addOperation("+", 1, [](int x, int y){ return x + y; });
    expression.addOperation("-", 1, [](int x, int y){ return x - y; });
    expression.addOperation("/", 2, [](int x, int y){ return x / y; });
    expression.addOperation("*", 2, [](int x, int y){ return x * y; });

    out << expression.evaluate();

    return 0;
}

Expression::Expression(const std::string& expression) {
    infixExpression = removeWhitespaces(expression);
}

void Expression::addOperation(const std::string& operation, int precedence, int (*function)(int, int)) {
    operationFunctions.emplace(operation, function);
    operationPrecedence.emplace(operation, precedence);
}

std::vector<std::string> Expression::createPostfixExpression() {

    std::vector<std::string> postfixExpression;
    std::stack<char> st;

    for (int i = 0; i < infixExpression.length(); i++) {
        if (isdigit(infixExpression[i])) {

            std::string buffer;

            for (; i < infixExpression.length() && (isdigit(infixExpression[i]) || infixExpression[i] == '.'); i++) {
                buffer += infixExpression[i];
            }

            postfixExpression.push_back(buffer);
            i--;
            continue;
        } else if(infixExpression[i] == '(') {
            st.push('(');
        } else if (infixExpression[i] == ')') {
            while (!st.empty() &&  st.top() != '(') {
                postfixExpression.emplace_back(1, st.top());
                st.pop();
            }
            st.pop();
        } else if (isOperator(infixExpression[i])) {
            if (st.empty() || st.top() == '(') {
                st.push(infixExpression[i]);
            } else {
                while (!st.empty() && st.top() != '(' && getPrecedence(infixExpression[i]) <= getPrecedence(st.top())) {
                    postfixExpression.emplace_back(1, st.top());
                    st.pop();
                }
                st.push(infixExpression[i]);
            }
        }
    }

    while (!st.empty()) {
        postfixExpression.emplace_back(1, st.top());
        st.pop();
    }

    return postfixExpression;
}


int Expression::evaluatePostfixExpression(const std::vector<std::string>& postfixExpression) {
    std::stack<int> st;

    for (const auto& item: postfixExpression) {
        if (isOperand(item)) {
            st.push(std::stoi(item));
        } else {
            int rightSide = st.top();
            st.pop();
            int leftSide = st.top();
            st.pop();
            st.push(computeOperation(item, leftSide, rightSide));
        }
    }
    return st.top();
}

int Expression::evaluate() {
    return evaluatePostfixExpression(createPostfixExpression());
}

int Expression::computeOperation(const std::string& operation, int leftSide, int rightSide) {
    auto result = operationFunctions.find(operation);
    return (result->second)(leftSide, rightSide);
}

bool Expression::isOperand(const std::string &s) {
    return std::all_of(s.begin(), s.end(), isdigit);
}

bool Expression::isOperator(char character) {
    return operationFunctions.find(std::string(1,character)) != operationFunctions.end();
}

int Expression::getPrecedence(char operation) {
    auto result = operationPrecedence.find(std::string(1, operation));

    return result->second;
}

std::string Expression::removeWhitespaces(const std::string& str) {
    std::string whiteSpacesRemoved;
    std::copy_if(str.begin(), str.end(), std::back_inserter(whiteSpacesRemoved), [](char c){ return !isspace(c); });
    return whiteSpacesRemoved;
}