Pagini recente » Cod sursa (job #610165) | Cod sursa (job #935004) | Cod sursa (job #996192) | Cod sursa (job #1135055) | Cod sursa (job #1426829)
#include <iostream>
#include <fstream>
#include <cstring>
#include <stack>
#include <queue>
#define MAXLEN 100001
//leaf = operand, root = operator
enum Type {leaf, root};
const char IN[] = "evaluare.in", OUT[] = "evaluare.out";
using namespace std;
char expr[MAXLEN], polish[MAXLEN];
//binary tree, if type is leaf then the relevant attribute is the operand value
//otherwise, the expression is analyzed by looking at the operator
struct node {
struct node *left, *right;
bool type;
char op;
long operand;
};
//true if c is an operator
inline bool isop(char c) {
return c == '+' || c == '-' || c == '/' || c == '*';
}
//true if c is a digit
inline bool isNum(char c) {
return c >= '0' && c <= '9';
}
//paranthesis have lowest(-1) level, + and - have level 0 and the highest are * and /
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);
}
//evaluates a tree
//if the current node is a root, then we evaluate the left and right children with the
//operator, otherwise if the current node is a leaf we return the value
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;
}
}
//transforms an infix notation into a polish notation
inline void polishTransform() {
char *srcP = expr, *dstP = polish;
//operator stack
stack<char> op;
while (*srcP != '\0') {
if (*srcP == ' ') { ++srcP; continue; }
//the start of a new expression, it is pushed to the stack to control precedence
if (*srcP == '(') { op.push(*srcP++); continue; }
//pop till we find the matching opening paranthesis
if (*srcP == ')') {
while (op.top() != '(') {
*dstP++ = ' ';
*dstP++ = op.top();
op.pop();
}
++srcP;
op.pop();
continue;
}
//pop until we find an operator of the same precedence or a paranthesis
if (isop(*srcP)) {
while (!op.empty() && getLvl(*srcP) <= getLvl(op.top())) {
*dstP++ = ' ';
*dstP++ = op.top();
op.pop();
}
//push the current operator to the stack
op.push(*srcP);
*dstP++ = ' ';
++srcP;
continue;
}
//put digits into the polish notation
while (isNum(*srcP)) *dstP++ = *srcP++;
}
//pop the highest level operators
while (!op.empty()) {
*dstP++ = ' ';
*dstP++ = op.top();
op.pop();
}
//null terminate string
*dstP = '\0';
}
//gets a number from a char sequence
inline long getNumber(char **p){
int nr = 0;
//while the current char is a digit we construct the number
while (isNum(**p)) {
//nr = nr * 10 + the actual value of the digit
nr = (nr << 3) + (nr << 1) + **p - '0';
++*p;
}
return nr;
}
//constructs the expression tree of a polish notation
node *makeTree(char e[]) {
char *p = e;
//the stack of expressions used to construct the final result
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;
}
//skip over whitespaces, they are used to separate multi-digit numbers
if (*p == ' ') { p++; continue; }
//construct a new leaf with the current number as it's value
node *t = new node();
t->type = leaf;
t->left = t->right = NULL;
t->operand = getNumber(&p);
//push it to the stack
treeStack.push(t);
}
//the root of the expression tree will be the only element left in the stack
node* final = treeStack.top(); treeStack.pop();
return final;
}
int main() {
readData();
polishTransform();
node *expressionTree = makeTree(polish);
FILE *fout = freopen(OUT, "w", stdout);
if (!fout) return 1;
printf("%d \n", treeEval(expressionTree));
fclose(stdout);
return 0;
}