Cod sursa(job #1298775)

Utilizator andreiagAndrei Galusca andreiag Data 23 decembrie 2014 05:42:21
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.55 kb
// 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;
}