Pagini recente » Cod sursa (job #3241520) | Cod sursa (job #427069) | Cod sursa (job #3289546) | Cod sursa (job #117097) | Cod sursa (job #1009550)
#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;
}