Cod sursa(job #1538946)

Utilizator paul-gPaul Grigoras paul-g Data 30 noiembrie 2015 01:20:19
Problema Evaluarea unei expresii Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 2.31 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;

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;
}