Cod sursa(job #1816421)

Utilizator alexnekiNechifor Alexandru alexneki Data 26 noiembrie 2016 14:17:46
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.79 kb
#include <iostream>
#include <fstream>
#include <cassert>

using namespace std;

int const linemax = 100000;

ifstream in("evaluare.in");
ofstream out("evaluare.out");

struct Symbol {
    char op; //+, -, *, / and @ in case the element is not an operator, but a number
    int priority;
    long number;
};

char line[linemax];
Symbol opstack[linemax], postfix[linemax];
int oppointer, postpointer;

void pushpostfix(Symbol el) {
  postfix[postpointer] = el;
  postpointer++;
  if (el.op == '@') {
    cout << el.number << " ";
  } else {
    cout << el.op << " ";
  }
}

void pushopstack(char ch) {
  if (ch == '(') {
    opstack[oppointer] = {'(', 10, 0};
    oppointer++;
  } else if (ch == ')') {
    while (0 < oppointer && opstack[oppointer - 1].op != '(') {
      pushpostfix(opstack[oppointer - 1]);
      oppointer--;
    }
    oppointer--; //also pop the '('
    assert(0 <= oppointer);
  } else {
    int chprio;
    if (ch == '+' || ch == '-') {
      chprio = 2;
    } else {
      chprio = 3;
    }
    while (0 < oppointer && opstack[oppointer - 1].op != '(' && chprio <= opstack[oppointer - 1].priority) {
      pushpostfix(opstack[oppointer - 1]);
      oppointer--;
    }

    opstack[oppointer] = {ch, chprio, 0};
    oppointer++;
  }
}

void infixtopostfix(char *line) {
  int i = 0;
  long number = 0;
  bool startednumber = false;
  while (line[i] != '\0') {
//    cout<<infix[i];
    if (line[i] == '(' || line[i] == ')' || line[i] == '+' || line[i] == '-' || line[i] == '*' || line[i] == '/') {
      if (startednumber) {
        pushpostfix({'@', 0, number});
        number = 0;
        startednumber = false;
      }
      pushopstack(line[i]);
    } else {
      startednumber = true;
      number = number * 10 + ((int) line[i] - 48);
    }
    i++;
  }
  if (startednumber) {
    pushpostfix({'@', 0, number});
  }
  while (0 < oppointer) {
    pushpostfix(opstack[oppointer - 1]);
    oppointer--;
  }
}

void evalpostfix(Symbol *postfix, int postpointer) {
  long eval[linemax];
  int evalpointer = 0;

  for (int i = 0; i < postpointer; i++) {
    if (postfix[i].op == '@') {
      eval[evalpointer] = postfix[i].number;
      evalpointer++;
    } else {
      assert(2 <= evalpointer);
      if (postfix[i].op == '+') {
        eval[evalpointer - 2] = eval[evalpointer - 2] + eval[evalpointer - 1];
      } else if (postfix[i].op == '-') {
        eval[evalpointer - 2] = eval[evalpointer - 2] - eval[evalpointer - 1];
      } else if (postfix[i].op == '*') {
        eval[evalpointer - 2] = eval[evalpointer - 2] * eval[evalpointer - 1];
      } else if (postfix[i].op == '/') {
        eval[evalpointer - 2] = eval[evalpointer - 2] / eval[evalpointer - 1];
      }
      evalpointer--;
    }
  }
  out<<eval[0]<<endl;
}

int main() {
  in >> line;
  infixtopostfix(line);
  evalpostfix(postfix, postpointer);
  return 0;
}