Pagini recente » Cod sursa (job #2322283) | Cod sursa (job #790947) | Cod sursa (job #2702140) | Cod sursa (job #610346) | Cod sursa (job #2108401)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <ctime>
#include <cstdlib>
#include <stack>
#define DN 10000000
#define LL long long
using namespace std;
stack<int> rpn, ops;
ifstream fin("evaluare.in");
ofstream fout("evaluare.out");
// ifstream fin("input.txt");
int op_hash(char op) {
switch(op) {
case '+': return -1;
case '-': return -2;
case '*': return -3;
case '/': return -4;
case '(': return -5;
case ')': return -6;
}
}
int op_priority(int op) {
if (op >= -2) return 1; // +-
return 2; // */
}
bool is_digit(char c) {
return c >= '0' && c <= '9';
}
int get_token(string &s, int &pos) {
if (!is_digit(s[pos])) {
return op_hash(s[pos++]);
}
int num = 0;
while(is_digit(s[pos]))
num = num * 10 + (s[pos++] - '0');
return num;
}
void push_operator(int op) {
if (op == -6) {
// in case of closed parenthesis, we pop all operators till the open one
while (!ops.empty() && ops.top() != -5) {
rpn.push(ops.top());
ops.pop();
}
if (!ops.empty())
ops.pop(); // pop the opening parenthesis
return;
}
if (op == -5) {
// opening parenthesis are just pushed on the operator stack
ops.push(op);
return;
}
while (!ops.empty() && ops.top() >= -4 && op_priority(ops.top()) >= op_priority(op)) {
rpn.push(ops.top());
ops.pop();
}
ops.push(op);
}
void reverse_polish(string &s) {
int pos = 0;
while (pos < s.size()) {
int token = get_token(s, pos);
if (token < 0) {
// token is an operator
push_operator(token);
} else {
// token is a number
rpn.push(token);
}
}
while(!ops.empty()) {
rpn.push(ops.top());
ops.pop();
}
}
int get_operand() {
// Returns the last operand from rpn, which can be the result of an expression
if (rpn.empty()) return 0; // this should never execute is rpn is valid
int token = rpn.top();
rpn.pop();
if (token < 0) {
// binary operator, needs 2 operands
int b = get_operand(), a = get_operand();
switch(token) {
case -1: return a + b;
case -2: return a - b;
case -3: return a * b;
case -4: return a / b;
}
}
return token;
}
int main()
{
string s;
fin >> s;
reverse_polish(s);
fout << get_operand();
return 0;
}