Pagini recente » Cod sursa (job #2292835) | Cod sursa (job #150768) | Cod sursa (job #2089494) | Cod sursa (job #1932168) | Cod sursa (job #1978255)
#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;
};
};
deque<node_data> to_polish(string &expression)
{
deque<node_data> polish;
deque<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_back(data);
} else if (operators_stack.empty() || operators_stack.back() == '(' || expression[i] == '(') {
operators_stack.push_back(expression[i]);
} else if (expression[i] == ')') {
while (operators_stack.back() != '(') {
data.type = OPERATOR;
data.op = operators_stack.back();
polish.push_back(data);
operators_stack.pop_back();
}
operators_stack.pop_back();
} else if (operators[operators_stack.back()] == operators[expression[i]]) {
data.type = OPERATOR;
data.op = operators_stack.back();
polish.push_back(data);
operators_stack.pop_back();
operators_stack.push_back(expression[i]);
} else if (operators[operators_stack.back()] > operators[expression[i]]) {
data.type = OPERATOR;
data.op = operators_stack.back();
polish.push_back(data);
operators_stack.pop_back();
i--;
} else if (operators[operators_stack.back()] < operators[expression[i]]) {
operators_stack.push_back(expression[i]);
}
}
while (!operators_stack.empty()) {
data.type = OPERATOR;
data.op = operators_stack.back();
polish.push_back(data);
operators_stack.pop_back();
}
return polish;
}
long eval_polish(deque<node_data> &polish)
{
node_data nd;
stack<long> results;
while (!polish.empty()) {
nd = polish.front();
polish.pop_front();
if (nd.type == OPERATOR) {
long val2 = results.top();
results.pop();
long val1 = results.top();
results.pop();
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 << nd.term << endl;
}
}
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);
long result = eval_polish(polish);
cout << result << "\n";
return 0;
}