Pagini recente » Cod sursa (job #1224057) | Cod sursa (job #3030641) | Cod sursa (job #1144817) | Cod sursa (job #2637389) | Cod sursa (job #1426812)
#include <iostream>
#include <fstream>
#include <cstring>
#include <stack>
#include <queue>
#define MAXLEN 100001
#define LVLMAX 2
//leaf = operand, root = operator
enum Type {leaf, root};
const char IN[] = "evaluare.in", OUT[] = "evaluare.out";
using namespace std;
char expr[MAXLEN], polish[MAXLEN];
struct node {
struct node *left, *right;
bool type;
char op;
long operand;
};
inline bool isop(char c) {
return c == '+' || c == '-' || c == '/' || c == '*';
}
inline bool isNum(char c) {
return c >= '0' && c <= '9';
}
inline int getLvl(char c) {
if (c == '+' || c == '-') return 0;
if (c == '*' || c == '/') return 1;
return -1;
}
inline void readData() {
FILE *fin = freopen(IN, "r", stdin);
if (!fin) return;
gets(expr);
fclose(stdin);
}
long treeEval(node *n) {
if (n->type == leaf) return n->operand;
switch (n->op) {
case '+': return treeEval(n->left) + treeEval(n->right); break;
case '-': return treeEval(n->left) - treeEval(n->right); break;
case '*': return treeEval(n->left) * treeEval(n->right); break;
case '/':return treeEval(n->left) / treeEval(n->right); break;
}
}
inline void polishTransform() {
char *srcP = expr, *dstP = polish;
stack<char> op;
while (*srcP != '\0') {
if (*srcP == ' ') { ++srcP; continue; }
//the start of a new expression is not relevant
if (*srcP == '(') { op.push(*srcP++); continue; }
//pop till we find the matching opening
if (*srcP == ')') {
while (op.top() != '(') {
*dstP++ = ' ';
*dstP++ = op.top();
op.pop();
}
++srcP;
op.pop();
continue;
}
//pop until we find a lower precedence operator
if (isop(*srcP)) {
while (!op.empty() && getLvl(*srcP) <= getLvl(op.top())) {
*dstP++ = ' ';
*dstP++ = op.top();
op.pop();
}
op.push(*srcP);
*dstP++ = ' ';
++srcP;
continue;
}
while (isNum(*srcP)) *dstP++ = *srcP++;
}
while (!op.empty()) {
*dstP++ = ' ';
*dstP++ = op.top();
op.pop();
}
*dstP = '\0';
}
inline long getNumber(char **p){
int nr = 0;
while (isNum(**p)) {
nr = (nr << 3) + (nr << 1) + **p - '0';
++*p;
}
return nr;
}
node *makeTree(char e[]) {
char *p = e;
stack<node*> treeStack;
while (*p != '\0') {
if (isop(*p)) {
//construct a new tree with this operand as its root
node* t = new node();
//children are the top 2 trees in the stack
t->right = treeStack.top(); treeStack.pop();
t->left = treeStack.top(); treeStack.pop();
t->type = root;
t->op = *p++;
treeStack.push(t);
continue;
}
if (*p == ' ') { p++; continue; }
node *t = new node();
t->type = leaf;
t->left = t->right = NULL;
t->operand = getNumber(&p);
treeStack.push(t);
}
node* final = treeStack.top(); treeStack.pop();
return final;
}
int main() {
readData();
polishTransform();
//cout << polish << endl;
node *expressionTree = makeTree(polish);
FILE *fout = freopen(OUT, "w", stdout);
if (!fout) return 1;
printf("%d \n", treeEval(expressionTree));
fclose(stdout);
return 0;
}