Cod sursa(job #1061579)

Utilizator L.DanielLungu Daniel L.Daniel Data 19 decembrie 2013 22:30:01
Problema Evaluarea unei expresii Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 2.29 kb
#include <fstream>
#include<string.h>
using namespace std;
#define MAXINT 10000000000
struct sir
{
	int val;
	char operant;
}b[1000000];
struct lista
{
	lista*st, *dr;
	int val;
	char op;
};
lista*prim = NULL;
lista*ult = NULL;
char c[1000000];
int n, k, v[1000000];
void add(int);
void schimbare()
{
	int i = 0;
	while (i < n)
	{
		if (c[i] >= '0'&&c[i] <= '9')
		{
			b[k].val = c[i] - '0';
			i++;
			b[k].operant = NULL;
			while (c[i] >= '0'&&c[i] <= '9')
			{
				b[k].val =b[k].val*10+c[i] - '0';
				i++;
			}
			k++;
		}
		else { b[k].operant = c[i];
		b[k].val = NULL;
		i++;
		k++;
		}
	}
}
void identificare()
{
	int i, l = 0;
	for (i = 0; i<k; i++)
	{
		if (b[i].operant == '(')
		{
			v[i] = 0;
			l = l + 10;
		}
		else if (b[i].operant == ')')
		{
			v[i] = 0;
			l = l - 10;
		}
		else if (b[i].val!=NULL) v[i] = MAXINT;
		else if (b[i].operant == '-' || b[i].operant == '+')v[i] = l + 1;
		else v[i] = l + 2;
	}
}
void RSD(int st, int dr)
{
	int x = MAXINT, i, l = -1;
	for (i = st; i <= dr; i++)
	if (x >= v[i] && v[i] != 0)
	{
		x = v[i];
		l = i;
	}
	if (l != -1)
	{
		add(l);
		RSD(st, l - 1);
		RSD(l + 1, dr);
	}



}
void add(int x)
{
	lista*q = new lista;
	if (b[x].val!=NULL)q->val = b[x].val;
	else q->op =b[x].operant;
	if (prim == NULL)
	{
		q->st = NULL;
		q->dr = NULL;
		prim = q;
		ult = q;
	}
	else
	{
		q->st = ult;
		q->dr = NULL;
		ult->dr = q;
		ult = q;
	}
}
void calcul()
{
	while (ult != prim)
	{
		lista*p = new lista;
		p = ult;
		while (p->op <= 0 && p->st != NULL)p = p->st;
		if (p->op == '+')
		{
			p->val = p->dr->val + p->dr->dr->val;
			p->op = NULL;
		}
		else if (p->op == '*')
		{
			p->val = p->dr->val * p->dr->dr->val;
			p->op = NULL;
		}
		else if (p->op == '-')
		{
			p->val = p->dr->val - p->dr->dr->val;
			p->op = NULL;
		}
		else if (p->op == '/')
		{
			p->val = p->dr->val / p->dr->dr->val;
			p->op = NULL;
		}
		if (p->dr->dr->dr == NULL)
		{
			ult = p;
			p->dr = NULL;
		}
		else {
			p->dr = p->dr->dr->dr;
			p->dr->st = p;
		}

	}
}
int main()
{
	ifstream f("evaluare.in");
	ofstream g("evaluare.out");
	f >> c;
	n = strlen(c);
	schimbare();
	identificare();
	RSD(0,k - 1);
	calcul();
	g << prim->val;
	return 0;
}