Pagini recente » Borderou de evaluare (job #2080863) | Cod sursa (job #2889528) | Borderou de evaluare (job #1330495) | Cod sursa (job #495243) | Cod sursa (job #3239873)
#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;
}