Cod sursa(job #1426812)

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