Pagini recente » Cod sursa (job #2309389) | Cod sursa (job #462367) | Cod sursa (job #1951226) | Cod sursa (job #1242838) | Cod sursa (job #1978295)
#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;
long long term;
};
};
struct node {
node_data *data;
node *left;
node *right;
};
void build_tree(node *root, deque<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.back().type == OPERAND) {
root->data->type = OPERAND;
root->data->term = polish.back().term;
} else {
root->data->type = OPERATOR;
root->data->op = polish.back().op;
is_operator = true;
}
polish.pop_back();
if (is_operator) {
root->right = new node;
build_tree(root->right, polish);
root->left = new node;
build_tree(root->left, polish);
}
}
long 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;
}
void free_tree(node *root)
{
if (root == nullptr) return ;
if (root->left != nullptr) {
free_tree(root->left);
}
if (root->right != nullptr) {
free_tree(root->right);
}
if (root->data != nullptr) {
delete root->data;
root->data = nullptr;
}
delete root;
root = nullptr;
}
deque<node_data> to_polish(string &expression)
{
deque<node_data> polish;
stack<char> operators_stack;
node_data data;
for (int i = 0; i < expression.size(); i++) {
//cout << "Before - OPERATOR STACK: ";
//cout << endl;
//cout << i << endl;
if (expression[i] >= '0' && expression[i] <= '9') {
//cout << "Number" << endl;
long 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_back(data);
//cout << "PUSH " << data.term << endl;
} else if ((operators_stack.empty() || operators_stack.top() == '(' || expression[i] == '(') && expression[i] != ')') {
//cout << "Emptry or (" << endl;
operators_stack.push(expression[i]);
} else if (expression[i] == ')') {
//cout << "End )" << endl;
while (operators_stack.top() != '(') {
data.type = OPERATOR;
data.op = operators_stack.top();
polish.push_back(data);
//cout << "PUSH " << data.op << endl;
operators_stack.pop();
}
operators_stack.pop();
} else if (operators[operators_stack.top()] == operators[expression[i]]) {
//cout << "Equal" << endl;
data.type = OPERATOR;
data.op = operators_stack.top();
polish.push_back(data);
//cout << "PUSH " << data.op << endl;
operators_stack.pop();
operators_stack.push(expression[i]);
} else if (operators[operators_stack.top()] > operators[expression[i]]) {
//cout << "Greater" << endl;
data.type = OPERATOR;
data.op = operators_stack.top();
polish.push_back(data);
//cout << "PUSH " << data.op << endl;
operators_stack.pop();
i--;
} else if (operators[operators_stack.top()] < operators[expression[i]]) {
//cout << "Less" << endl;
operators_stack.push(expression[i]);
}
//cout << "After - OPERATOR STACK: ";
//cout << endl << endl;
}
while (!operators_stack.empty()) {
data.type = OPERATOR;
data.op = operators_stack.top();
polish.push_back(data);
//cout << "!PUSH " << data.op << endl;
operators_stack.pop();
}
return polish;
}
long long eval_polish(deque<node_data> &polish)
{
node_data nd;
stack<long long> results;
while (!polish.empty()) {
nd = polish.front();
polish.pop_front();
if (nd.type == OPERATOR) {
//if (results.empty()) throw("Results stack empty");
long long val2 = results.top();
results.pop();
//if (results.empty()) throw("Results stack empty");
long long val1 = results.top();
results.pop();
//cout << "EVAL " << val1 << nd.op << val2 << endl;
switch (nd.op) {
case '+':
results.push(val1 + val2);
break;
case '-':
results.push(val1 - val2);
break;
case '*':
results.push(val1 * val2);
break;
case '/':
results.push(val1 / val2);
break;
}
////cout << nd.op << endl;
} else if (nd.type == OPERAND) {
results.push(nd.term);
//cout << "PUSH " << nd.term << endl;
////cout << nd.term << endl;
}
}
//if (results.empty()) throw("Results stack empty");
return results.top();
}
int main() {
freopen("evaluare.in", "r", stdin);
freopen("evaluare.out", "w", stdout);
string expr;
cin >> expr;
init_polish_translator();
deque<node_data> polish = to_polish(expr);
//cout << "EVAL:" << endl;
//long long result = eval_polish(polish);
node *root = new node;
build_tree(root, polish);
long long result = eval_tree(root);
cout << result << "\n";
free_tree(root);
return 0;
}