Pagini recente » Cod sursa (job #262775) | infoarena - comunitate informatica, concursuri de programare | Cod sursa (job #332890) | Cod sursa (job #2657473) | Cod sursa (job #1978217)
#include <bits/stdc++.h>
using namespace std;
#define long long long
#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;
long 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);
}
}
long 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') {
long 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);
long result = eval_tree(root);
cout << result << "\n";
return 0;
}