Cod sursa(job #807024)

Utilizator BitOneSAlexandru BitOne Data 3 noiembrie 2012 22:14:00
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include <string>
#include <cstdlib>
#include <fstream>
#define ERROR -(1<<30)

using namespace std;

struct ExpTreeNode
{
	char op;
	int value;
	ExpTreeNode *left, *right;
	
	ExpTreeNode() : left(NULL), right(NULL) {}
	ExpTreeNode(char _op, ExpTreeNode* _left, ExpTreeNode* _right)   : op(_op), value(ERROR),  left(_left), right(_right) {}
	ExpTreeNode(int _value, ExpTreeNode* _left, ExpTreeNode* _right) : op(','), value(_value), left(_left), right(_right) {}
};

string exp;
string::const_iterator it, iend;
const string opLevel[] = {"+-", "*/", "^"};

ExpTreeNode* createTree(int level)
{
	int x;
	ExpTreeNode* node_ptr;
	
	if(2 == level)
	{
		if('(' == *it)
		{
			++it;
			node_ptr = createTree(0);
			++it;
		}
		else {
				for(x = 0; it < iend && *it >= '0' && *iend <= '9'; ++it)
				{
					x = x*10 + *it - '0';
				}
				
				node_ptr =new ExpTreeNode(x, NULL, NULL);
			 }
	}
	else {
			for(node_ptr = createTree(level+1); it < iend && string::npos != opLevel[level].find(*it);)
			{
				char op = *(it++);
				node_ptr = new ExpTreeNode(op, node_ptr, createTree(level+1));
			}
		 }
	
	return node_ptr;
}

int eval(ExpTreeNode* root)
{
	if(NULL == root) return 0;
	if(NULL == root->left) return root->value;
	
	int a = eval(root->left),  b = eval(root->right);
	
	switch(root->op)
	{
		case '+' : return a+b;
		case '-' : return a-b;
		case '*' : return a*b;
		case '/' : return a/b;
		default  : return ERROR;
	}
}

int main()
{
	ifstream in("evaluare.in");
	ofstream out("evaluare.out");

	getline(in, exp);
	it = exp.begin(), iend = exp.end();
	
	out << eval(createTree(0)) << '\n';
	
	return EXIT_SUCCESS;
}