Cod sursa(job #3239873)

Utilizator ChopinFLazar Alexandru ChopinF Data 8 august 2024 12:40:02
Problema Evaluarea unei expresii Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.53 kb
#include <bits/stdc++.h>
#include <vector>
using namespace std;
std::string file = "evaluare";
std::ifstream fin(file + ".in");
std::ofstream fout(file + ".out");
// #define fin std::cin
// #define fout std::cout
struct node {
  std::string value;
  node *left;
  node *right;
  node(std::string val) : value(val), left(nullptr), right(nullptr){};
};
node *constructTree(const std::vector<std::string> &postfix) {
  std::stack<node *> st;
  for (const auto &token : postfix) {
    if (isdigit(token[0])) {
      st.push(new node(token));
    } else {
      node *n = new node(token);
      n->right = st.top();
      st.pop();
      n->left = st.top();
      st.pop();
      st.push(n);
    }
  }
  return st.top();
}

int evaluate(node *root) {
  // Daca e frunza
  if (!root->left && !root->right) {
    return stoi(root->value);
  }
  int leftVal = evaluate(root->left);
  int rightVal = evaluate(root->right);
  if (root->value == "+")
    return leftVal + rightVal;
  if (root->value == "-")
    return leftVal - rightVal;
  if (root->value == "*")
    return leftVal * rightVal;
  if (root->value == "/")
    return leftVal / rightVal;

  return 0;
}

int precedence(char op) {
  if (op == '+' || op == '-')
    return 1;
  if (op == '*' || op == '/')
    return 2;
  return 0;
}

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

vector<string> infixToPostfix(const string &expr) {
  stack<char> ops;
  vector<string> postfix;
  for (int i = 0; i < expr.size(); i++) {
    char c = expr[i];

    if (isdigit(c)) {
      string num;
      while (i < expr.size() && isdigit(expr[i])) {
        num += expr[i++];
      }
      i--; // Adjust because the loop will increment i
      postfix.push_back(num);
    } else if (c == '(') {
      ops.push(c);
    } else if (c == ')') {
      while (!ops.empty() && ops.top() != '(') {
        postfix.push_back(string(1, ops.top()));
        ops.pop();
      }
      ops.pop(); // Remove the '(' from stack
    } else if (isOperator(c)) {
      while (!ops.empty() && precedence(ops.top()) >= precedence(c)) {
        postfix.push_back(string(1, ops.top()));
        ops.pop();
      }
      ops.push(c);
    }
  }

  while (!ops.empty()) {
    postfix.push_back(string(1, ops.top()));
    ops.pop();
  }

  return postfix;
}

int32_t main(int32_t argc, char *argv[]) {
  ios_base::sync_with_stdio(false);
  fin.tie(0);
  fout.tie(0);
  std::string expr;
  fin >> expr;
  std::vector<std::string> postfix = infixToPostfix(expr);
  node *root = constructTree(postfix);
  fout << evaluate(root) << "\n";
  return 0;
}