Cod sursa(job #1005331)

Utilizator gabrieligabrieli gabrieli Data 4 octombrie 2013 20:22:32
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <fstream>
using namespace std;

constexpr size_t MAX_SIZE = 100010;
const char operators[2][3] = { "+-", "*/"};
const int LMAX = 2;
char expr[MAX_SIZE];

struct node
{
	char op;
	int val;
	node *left, * right;

	node(char op = 0, int val = 0,
			node *left = nullptr, node *right = nullptr)
		: op(op), val(val), left(left), right(right) {}

	~node()
	{
		delete left;
		delete right;
	}
};

void next_token(const char *&p)
{
	if (*p == '\0') return;
	for (++p; isspace(*p); ++p);
}

node* create_expr_tree(const size_t level, const char *&p)
{
	node *x, *y;

	if (level == LMAX)
	{
		if (*p == '(')
		{
			next_token(p);
			x = create_expr_tree(0, p);
			next_token(p);
		}
		else
		{
			for (x = new node(0, 0, nullptr, nullptr);
					'0' <= *p && *p <= '9'; next_token(p))
				x->val = x->val * 10 + (*p) - '0';
		}
	}
	else
	{
		for (x = create_expr_tree(level+1, p);
				*p != '\0' && strchr(operators[level], *p); x = y)
		{
			char op = *p;
			next_token(p);
			y = new node(op, 0, x, create_expr_tree(level+1, p));
		}
	}

	return x;
}

int evaluate(const node *tree)
{
	switch(tree->op)
	{
		case '+': return evaluate(tree->left) + evaluate(tree->right);
		case '-': return evaluate(tree->left) - evaluate(tree->right);
		case '*': return evaluate(tree->left) * evaluate(tree->right);
		case '/': return evaluate(tree->left) / evaluate(tree->right);
		default:  return tree->val;
	}
}

int main()
{
	FILE *in = fopen("evaluare.in", "r"),
		 *out = fopen("evaluare.out", "w");

	fgets(expr, 100001, in);

	const char *p = expr;
	node *root = create_expr_tree(0, p);
	int result = evaluate(root);
	delete root;

	fprintf(out, "%d\n", result); 

	fclose(in);
	fclose(out);
	return 0;
}