Pagini recente » Cod sursa (job #2489598) | Cod sursa (job #914200) | Cod sursa (job #243796) | Cod sursa (job #2031548) | Cod sursa (job #1298775)
// shunting_yeard rpn
#include <iostream>
#include <fstream>
#include <string>
#include <stack>
#include <queue>
using namespace std;
queue<int> nums, ops, ord;
string A;
int pos = 0;
inline int compute(int a, int b, int oper) {
switch (oper) {
case 1: return a+b;
case 2: return a-b;
case 3: return a*b;
case 4: return a/b;
default: return 0;
}
}
int eval_rpn() {
stack<int> work_bench;
while(!ord.empty()) {
int x = ord.front();
ord.pop();
if (x) {
int a = nums.front();
nums.pop();
work_bench.push(a);
}
else {
int oper = ops.front(); ops.pop();
int b = work_bench.top(); work_bench.pop();
int a = work_bench.top(); work_bench.pop();
work_bench.push(compute(a, b, oper));
}
}
return work_bench.top();
}
/* ------ BEGIN DEBUG ------*/
char get_oper[] = {'#', '+','-','*','/'};
void print_rpn_expression() {
cout << "Sizes check: tot,nums,ops: " << ord.size() << ' ' << nums.size() << ' ' << ops.size() << '\n';
while(!ord.empty()) {
int x = ord.front(); ord.pop();
if (x) {
cout << nums.front() << ' ';
nums.pop();
} else {
cout << get_oper[ops.front()] << ' ';
ops.pop();
}
}
cout << '\n';
}
/* ------ END DEBUG ------*/
inline int parse_num() {
int r = 0;
while(pos < A.length() && A[pos] >= '0' && A[pos] <= '9') {
r = r*10 + A[pos] - '0';
pos++;
}
return r;
}
void parse_expression() {
stack<int> S;
while(pos < A.length()) {
int c = A[pos];
if (c == '(') {
S.push(0); pos++;
} else if (c == ')') {
while(S.top() != 0) {
ord.push(0); // queue operation;
ops.push(S.top());
S.pop();
}
S.pop();
pos++;
} else if (c == '+' || c == '-') {
int x = (c == '+' ? 1 : 2);
while (!S.empty() && S.top() != 0) {
ord.push(0);
ops.push(S.top());
S.pop();
}
S.push(x);
pos++;
} else if (c == '*' || c == '/') {
int x = (c == '*' ? 3 : 4);
while (!S.empty() && (S.top() != 0) && (S.top() > 2)) {
ord.push(0);
ops.push(S.top());
S.pop();
}
S.push(x);
pos++;
} else if (c >= '0' && c <= '9') {
ord.push(1); // queue number
nums.push(parse_num());
}
}
while(!S.empty()) {
ord.push(0);
ops.push(S.top());
S.pop();
}
}
int main()
{
ifstream f ("evaluare.in");
ofstream g ("evaluare.out");
f >> A;
parse_expression();
int answer = eval_rpn();
g << answer << '\n';
//print_rpn_expression();
return 0;
}