Cod sursa(job #676114)

Utilizator sory1806Sandu Sorina-Gabriela sory1806 Data 8 februarie 2012 18:03:38
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.19 kb

#include <cstdio>
#include <string.h>
#include <list>
#include <stack>
#include <cctype>

#define _MAX_LEN 100010

using namespace std;

bool is_operator(char c) {
  return (c == '+' || c == '-' || c == '*' || c == '/');
}

//  1 for + and -
//  2 for * and /
//  0 for wrong parameter
int priority(char c) {
  if(c == '+' || c == '-')
    return 1;
  if(c == '*' || c == '/')
    return 2;
  return 0;
}

list <char *> infix_to_postfix(char *infix) {
  stack <char *> s;
  list <char *> postfix;
  char *p;
  bool digit = false;

  while(*infix) {

    if(isdigit(*infix)) {
      if(!digit) {
	postfix.push_back(infix);
	digit = true;
      }
    }
    else {

      if(*infix == '(')
        s.push(infix);
      if(*infix == ')') {
	while(!s.empty() && *(p = s.top()) != '(') {
	  postfix.push_back(p);
	  s.pop();
	}
	if(*p == '(')
	  s.pop();
      }
      if(is_operator(*infix)) {
	while(!s.empty() && priority(*(p = s.top())) >= priority(*infix)) {
	  postfix.push_back(p);
	  s.pop();
	}
	s.push(infix);
      }

      digit = false;
    }

    infix ++;
  }
  while(!s.empty()) {
    postfix.push_back(s.top());
    s.pop();
  }
  return postfix;
}

int get_number(char *s) {
  int x = 0;

  while(isdigit(*s)) {
    x = x * 10 + *s - '0';
    s ++;
  }

  return x;
}

int calc_rez(int a, int b, char op) {

  if(op == '+')
    return a + b;
  if(op == '-')
    return a - b;
  if(op == '*')
    return a * b;
  if(op == '/')
    return a / b;

  return 0;
}

int eval_postfix(list <char *> li) {

  char *p;
  int op1, op2;
  stack <int> s;

  while(!li.empty()) {
    p = li.front();

    if(!isdigit(*p)) {
      op2 = s.top();
      s.pop();
      op1 = s.top();
      s.pop();

      s.push(calc_rez(op1, op2, *p));
 //     printf("%d %c %d = %d\n", op1, *p, op2, calc_rez(op1, op2, *p));

//      printf("%c\n", *p);
    }
    else {
      s.push(get_number(p));

 //     printf("%d\n", get_number(p));
    }

    li.pop_front();
  }

  return s.top();
}

int main() {

  char exp[_MAX_LEN];
  list <char *> postfix;

  freopen("evaluare.in", "r", stdin);
  freopen("evaluare.out", "w", stdout);

  fgets(exp, _MAX_LEN, stdin);
  postfix = infix_to_postfix(exp);

  printf("%d\n", eval_postfix(postfix));

  return 0;
}