Pagini recente » Cod sursa (job #1408945) | Cod sursa (job #848754) | Cod sursa (job #731454) | Istoria paginii runda/10din10 | Cod sursa (job #1538946)
// 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;
int eval(const vector<string>& ts) {
int p = 0;
stack<int> s;
for (const string& t : ts) {
if (isdigit(t[0])) {
int num;
stringstream ss;
ss << t;
ss >> num;
s.push(num);
continue;
}
int b = s.top();
s.pop();
int a = s.top();
s.pop();
int res = 0;
switch (t[0]) {
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 << "'" << endl;
}
s.push(res);
}
return s.top();
}
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<string> convert(string infix) {
vector<char> ts;
for (char s : infix) {
if (s != ' ')
ts.push_back(s);
}
vector<string> output;
stack<char> ops;
bool havenum = false;
int num = 0;
for (int i = 0; i < ts.size(); i++) {
char t = ts[i];
if (isdigit(t)) {
string num;
while (i < ts.size() && isdigit(ts[i])) {
num += ts[i];
i++;
}
i--;
output.push_back(num);
continue;
}
if (t == '(') {
ops.push(t);
continue;
}
if (t == ')') {
while (ops.top() != '(') {
output.push_back(string(1, ops.top()));
ops.pop();
}
ops.pop();
continue;
}
while (!ops.empty()
&& ops.top() != '('
&& prec(t) <= prec(ops.top()) ) {
output.push_back(string(1, ops.top()));
ops.pop();
}
ops.push(t);
}
while (!ops.empty()) {
output.push_back(string(1, ops.top()));
ops.pop();
}
return output;
}
int main() {
ifstream f{"evaluare.in"};
ofstream g{"evaluare.out"};
string expr;
f >> expr;
//auto conv = convert(expr);
//for (const auto s : conv)
//cout << s << " ";
g << eval(convert(expr));
return 0;
}