Cod sursa(job #1426829)

Utilizator GilgodRobert B Gilgod Data 30 aprilie 2015 18:35:19
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 4.25 kb
#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;
}