Pagini recente » Cod sursa (job #2399372) | Rating Giurcanu Codrin (ZifferRhein) | Cod sursa (job #1588909) | Cod sursa (job #1741869) | Cod sursa (job #1538948)
// http://www.infoarena.ro/problema/evaluare
// https://en.wikipedia.org/wiki/Reverse_Polish_notation
#include <vector>
#include <stack>
#include <string>
#include <iostream>
#include <fstream>
#include <sstream>
using namespace std;
struct term {
int num;
char op;
explicit term(int _num) : num(_num), op(0) {}
explicit term(char _op) : num(-1), op(_op) {}
bool isOp() const {
return op != 0;
}
};
int eval(const vector<term>& ts) {
int p = 0;
stack<int> s;
for (const term& t : ts) {
if (!t.isOp()) {
s.push(t.num);
continue;
}
int b = s.top();
s.pop();
int a = s.top();
s.pop();
int res = 0;
switch (t.op) {
case '+':
res = a + b;
break;
case '-':
res = a - b;
break;
case '*':
res = a * b;
break;
case '/':
res = a / b;
break;
default:
cerr << "Unexpected token '" << t.op << "'" << endl;
}
s.push(res);
}
return s.top();
}
inline int prec(char t) {
switch (t) {
case '+':
case '-':
return 10;
case '*':
case '/':
return 100;
default:
cerr << "Unexpected token " << t << endl;
}
}
// convert infix expression to postfix expression
vector<term> convert(string infix) {
vector<char> ts;
for (char s : infix) {
if (s != ' ')
ts.push_back(s);
}
vector<term> output;
stack<char> ops;
for (int i = 0; i < ts.size(); i++) {
char t = ts[i];
if (isdigit(t)) {
int num = 0;
while (i < ts.size() && isdigit(ts[i])) {
num = num * 10 + (ts[i] - '0');
i++;
}
i--;
output.push_back(term(num));
continue;
}
if (t == '(') {
ops.push(t);
continue;
}
if (t == ')') {
while (ops.top() != '(') {
output.push_back(term(ops.top()));
ops.pop();
}
ops.pop();
continue;
}
while (!ops.empty()
&& ops.top() != '('
&& prec(t) <= prec(ops.top()) ) {
output.push_back(term(ops.top()));
ops.pop();
}
ops.push(t);
}
while (!ops.empty()) {
output.push_back(term(ops.top()));
ops.pop();
}
return output;
}
int main() {
ifstream f{"evaluare.in"};
ofstream g{"evaluare.out"};
string expr;
f >> expr;
//auto ts = convert(expr);
//for (auto& t : ts)
//std::cout << t.num << " " << t.op << std::endl;
g << eval(convert(expr));
return 0;
}