Pagini recente » Cod sursa (job #178815) | Cod sursa (job #197675) | Cod sursa (job #551213) | Cod sursa (job #169337) | Cod sursa (job #1978294)
#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;
};
};
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);
cout << result << "\n";
return 0;
}