Pagini recente » Cod sursa (job #180006) | Cod sursa (job #2215488) | Cod sursa (job #2361366) | Borderou de evaluare (job #2288892) | Cod sursa (job #1732045)
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <unordered_map>
#include <utility>
#include <assert.h>
char str[100000];
std::unordered_map<char, int> precedence;
bool is_operator (char a) {
if ( a == '+' ||
a == '-' ||
a == '*' ||
a == '/' ||
a == '^') {
return true;
}
return false;
}
std::string infix_to_postfix (std::string infix) {
int size = infix.length();
std::stack <char> stack;
bool ok = false;
std::string postfix;
int num = 0;
for (int i = 0; i < size; ++i) {
if (infix[i] == ' ') {
continue;
}
while (infix[i] >= '0' && infix[i] <= '9') {
ok = true;
num = num * 10 + (infix[i] - '0');
++i;
}
if (ok) {
postfix += std::to_string (num);
postfix += " ";
ok = false;
num = 0;
}
if (infix[i] == '(') {
stack.push (infix[i]);
continue;
}
if (is_operator (infix[i])) {
while (!stack.empty() && is_operator (stack.top()) &&
precedence[infix[i]] <= precedence[stack.top()]) {
postfix += stack.top();
postfix += " ";
stack.pop();
}
stack.push (infix[i]);
continue;
}
if (infix[i] == ')') {
while (is_operator (stack.top())) {
postfix += stack.top();
postfix += " ";
stack.pop();
}
assert (stack.top() == '(');
stack.pop();
continue;
}
}
while (!stack.empty()) {
assert (is_operator (stack.top()));
postfix += stack.top();
postfix += " ";
stack.pop();
}
return postfix;
}
long do_op (int a, int b, char op) {
switch (op) {
case '+':
return a + b;
break;
case '-':
return a - b;
break;
case '*':
return a * b;
break;
case '/':
return (float)a / b;
break;
default:
return -1.0;
}
}
long evaluate (std::string postfix) {
int size = postfix.size();
int num = 0;
bool ok = false;
std::stack <long> stack;
for (int i = 0; i < size; ++i) {
while (postfix[i] >= '0' && postfix[i] <= '9') {
ok = true;
num = num * 10 + (postfix[i] - '0');
++i;
}
if (ok) {
stack.push (num);
ok = false;
num = 0;
}
if (is_operator (postfix[i])) {
assert (stack.size() >= 2);
int o1, o2;
o1 = stack.top();
stack.pop();
o2 = stack.top();
stack.pop();
stack.push (do_op (o2, o1, postfix[i]));
}
}
assert (stack.size() == 1);
return stack.top();
}
int main() {
precedence.insert (std::pair<char, int> ('+', 1));
precedence.insert (std::pair<char, int> ('-', 1));
precedence.insert (std::pair<char, int> ('*', 2));
precedence.insert (std::pair<char, int> ('/', 2));
precedence.insert (std::pair<char, int> ('^', 3));
std::ifstream fin ("evaluare.in");
std::ofstream fout ("evaluare.out");
fin.getline (str, 100000);
std::string infix (str);
fout << evaluate (infix_to_postfix (infix)) << "\n";
fout.close();
fin.close();
return 0;
}