Cod sursa(job #1538948)

Utilizator paul-gPaul Grigoras paul-g Data 30 noiembrie 2015 01:36:44
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.41 kb
// 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;
}