Cod sursa(job #1009550)

Utilizator andra23Laura Draghici andra23 Data 13 octombrie 2013 14:04:11
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 4.12 kb
#include <cstring>
#include <fstream>
#include <iostream>
#include <sstream>
#include <stack>

using namespace std;

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

class Node {
public:
  char type;
  char op;
  int num;
  Node *left, *right;
  Node(char type, char op, int num, Node *left, Node *right) : type(type),
    op(op), num(num), left(left), right(right) {}
};

class ExpressionConverter {
  int priority(char c) {
    if (c == '+' || c == '-') {
      return 1;
    } else {
      return 2;
    }
  }

  public:
  string convert(string &infix) {
    stringstream postfix;
    stack <char> s;
    for (int i = 0; i < infix.size();) {
      char c = infix[i];
      if (isdigit(c)) {
        int x = 0;
        while (i < infix.size() && isdigit(infix[i])) {
          x = x*10 + infix[i] - '0';
          i++;
        }
        postfix << x;
        postfix << ' ';
      } else {
        if (isOperator(c)) {
          while (!s.empty() && isOperator(s.top()) &&
              priority(s.top()) >= priority(c)) {
            postfix << s.top();
            postfix << ' ';
            s.pop();
          }
          s.push(c);
        } else if (c == '(') {
          s.push(c);
        } else if (c == ')') {
          while (!s.empty() && s.top() != '(') {
            postfix << s.top();
            postfix << ' ';
            s.pop();
          }
          if (s.empty()) {
            cout << "Incorrectly paranthesised expression!" << endl;
          } else {
            s.pop();
          }
        } else {
          cout << "Unknown character: " << c << endl;
        }
        ++i;
      }
    }
    while (!s.empty()) {
      postfix << s.top();
      postfix << ' ';
      s.pop();
    }
    return postfix.str();
  }
};

class Evaluator {

  int operation(int x, int y, char op) {
    if (op == '+') {
      return x + y;
    } else if (op == '-') {
      return x - y;
    } else if (op == '*') {
      return x * y;
    } else if (op == '/') {
      return x / y;
    }
  }

  public:
  int evaluate(string &postfix) {
    int result = 0;
    stack<int> s;
    for (int i = 0; i < postfix.size(); ) {
      char c = postfix[i];
      if (c == ' ') {
        i++;
      } else if (isdigit(c)) {
        int x = 0;
        while (i < postfix.size() && isdigit(postfix[i])) {
          x = x*10 + postfix[i] - '0';
          i++;
        }
        s.push(x);
      } else if (isOperator(c)) {
        int x = s.top();
        s.pop();
        int y = s.top();
        s.pop();
        s.push(operation(y, x, c));
        i++;
      } else {
        cout << "Unknown character: " << c << endl;
        i++;
      }
    }
    return s.top();
  }

  int evaluate(Node *root) {
    if (root->type == 'd') {
      return root->num;
    } else {
      return operation(evaluate(root->left), evaluate(root->right), root->op);
    }
  }
};

class ExpressionTreeBuilder {
public:
  Node* build(string &postfix) {
    stack<Node*> s;
    for (int i = 0; i < postfix.size(); ) {
      char c = postfix[i];
      if (c == ' ') {
        i++;
      } else if (isdigit(c)) {
        int x = 0;
        while (i < postfix.size() && isdigit(postfix[i])) {
          x = x*10 + postfix[i] - '0';
          i++;
        }
        s.push(new Node('d', ' ', x, NULL, NULL));
      } else if (isOperator(c)) {
        Node *x = s.top();
        s.pop();
        Node *y = s.top();
        s.pop();
        s.push(new Node('t', c, -1, y, x));
        i++;
      } else {
        cout << "Unknown character: " << c << endl;
        i++;
      }
    }
    return s.top();
  }
};

int main() {
  ifstream f("evaluare.in");
  string infix;
  f >> infix;
  ofstream g("evaluare.out");

  ExpressionConverter converter;
  string postfix = converter.convert(infix);
  //cout << "Postfix expression: " << postfix << endl;

  Evaluator evaluator;
  g << evaluator.evaluate(postfix) << endl;
  //cout << "Evaluation result: " << evaluator.evaluate(postfix) << endl;

  //ExpressionTreeBuilder treeBuilder;
  //Node *root = treeBuilder.build(postfix);
  //g << evaluator.evaluate(root) << endl;
  //cout << "Evaluation result using trees: " << evaluator.evaluate(root) << endl;

  return 0;
}