Cod sursa(job #1978216)

Utilizator LittleWhoFeraru Mihail LittleWho Data 7 mai 2017 09:36:39
Problema Evaluarea unei expresii Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 3.91 kb
#include <bits/stdc++.h>

using namespace std;

#define OPERATOR 1
#define OPERAND 2

unordered_map<char, int> operators;
void init_polish_translator()
{
    operators['+'] = 1;
    operators['-'] = 1;
    operators['*'] = 2;
    operators['/'] = 2;
}

struct node_data {
    char type;
    union {
        char op;
        int term;
    };
};

struct node {
    node_data *data;
    node *left;
    node *right;
};

void build_tree(node *root, stack<node_data> &polish)
{
    root->data = nullptr;
    root->right = nullptr;
    root->left = nullptr;

    if (polish.empty()) return ;

    bool is_operator = false;
    root->data =  new node_data;
    if (polish.top().type == OPERAND) {
        root->data->type = OPERAND;
        root->data->term = polish.top().term;
    } else {
        root->data->type = OPERATOR;
        root->data->op = polish.top().op;
        is_operator = true;
    }
    polish.pop();

    if (is_operator) {
        root->right = new node;
        build_tree(root->right, polish);

        root->left = new node;
        build_tree(root->left, polish);
    }
}

int eval_tree(node *root)
{
    if (root == nullptr) throw("Null pointer in expression tree.");
    if (root->data->type == OPERATOR) {
        switch (root->data->op) {
            case '+':
                return eval_tree(root->left) + eval_tree(root->right);
                break;
            case '-':
                return eval_tree(root->left) - eval_tree(root->right);
                break;
            case '*':
                return eval_tree(root->left) * eval_tree(root->right);
                break;
            case '/':
                return eval_tree(root->left) / eval_tree(root->right);
                break;
        }
    }

    return root->data->term;
}

stack<node_data> to_polish(string expression)
{
    stack<node_data> polish;
    stack<char> operators_stack;

    node_data data;
    for (int i = 0; i < expression.size(); i++) {
        if (expression[i] >= '0' && expression[i] <= '9') {
            int number = 0;
            while (expression[i] >= '0' && expression[i] <= '9') {
                number *= 10;
                number += expression[i] - '0';
                i++;
            }
            i--;

            data.type = OPERAND;
            data.term = number;
            polish.push(data);
        } else if (operators_stack.empty() || operators_stack.top() == '(' || expression[i] == '(') {
            operators_stack.push(expression[i]);
        } else if (expression[i] == ')') {
            while (operators_stack.top() != '(') {
                data.type = OPERATOR;
                data.op = operators_stack.top();
                polish.push(data);
                operators_stack.pop();
            }
            operators_stack.pop();
        } else if (operators[operators_stack.top()] == operators[expression[i]]) {
            data.type = OPERATOR;
            data.op = operators_stack.top();
            polish.push(data);
            operators_stack.pop();
            operators_stack.push(expression[i]);
        } else if (operators[operators_stack.top()] > operators[expression[i]]) {
            data.type = OPERATOR;
            data.op = operators_stack.top();
            polish.push(data);
            operators_stack.pop();
            i--;
        } else if (operators[operators_stack.top()] < operators[expression[i]]) {
            operators_stack.push(expression[i]);
        }
    }

    while (!operators_stack.empty()) {
        data.type = OPERATOR;
        data.op = operators_stack.top();
        polish.push(data);
        operators_stack.pop();
    }

    return polish;
}

int main() {
    freopen("evaluare.in", "r", stdin);
    freopen("evaluare.out", "w", stdout);

    string expr;
    cin >> expr;

    init_polish_translator();
    stack<node_data> polish = to_polish(expr);

    node *root = new node;
    build_tree(root, polish);

    int result = eval_tree(root);
    cout << result << "\n";

    return 0;
}