Cod sursa(job #713860)

Utilizator nytr0gennytr0gen nytr0gen Data 15 martie 2012 01:29:55
Problema Evaluarea unei expresii Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.25 kb
#include<fstream>
#include<cstring>
using namespace std;

const int MAX = 100010;
char S[MAX], *p = S;

typedef short shorty;
typedef char  mini;
typedef shorty huge[MAX];

/* Evaluarea Ecautiei */
void eval(huge);
void termen(huge);
void factor(huge);
/* Sfarsit Evaluarea Ecuatiei */

/* Functii Numere Mari */
void sum(huge, huge);
void dif(huge, huge);
void product(huge, huge);
void divide(huge, huge);
void factorial(huge);
char cmp(const huge, const huge);
/* Sfarsit Functi Numere Mari */

int main() {
	ifstream fin("evaluare.in");
		fin.get(S, MAX);
	fin.close();
	
	huge r; shorty i; eval(r);
	ofstream fout("evaluare.out");
		for(i = r[0]; i > 0; --i) 
			fout<<r[i];
	fout.close();
	
	return 0;
}

/* Evaluarea Ecautiei */
void eval(huge r) {
	huge t; termen(r);
	while(*p == '+' || *p == '-') {
		switch(*p++) {
			case '+': termen(t); sum(r, t); break;
			case '-': termen(t); dif(r, t); break;
		}
	}
}

void termen(huge r) {
	huge t; factor(r);
	while(*p == '*' || *p == '/') {
		switch(*p++) {
			case '*': factor(t); product(r, t); break;
			case '/': factor(t); divide(r, t); break;
		}
	}
}

void factor(huge r) {
    if(*p == '(') {
        ++p; eval(r); ++p;
    } else {
		static shorty i;
		r[0] = strspn(p, "0123456789");
		for(i = r[0]; i > 0; --i) r[i] = *p++-'0';
    }
	if(*p == '!') {
		factorial(r); ++p;
	}
}
/* Sfarsit Evaluarea Ecuatiei */

/* Functii Numere Mari */
void sum(huge a, huge b) {   
    static shorty i; 
	static mini t;
	
    if(a[0] < b[0]) {for(i = a[0]+1; i <= b[0]; ++i) a[i] = 0; a[0] = b[0];}
    else            {for(i = b[0]+1; i <= a[0]; ++i) b[i] = 0;}
	
	for(i = 1, t = 0; i <= a[0]; a[i++] %= 10, t /= 10)
		t += (a[i]+=b[i]+t);
	if(t) a[++a[0]] = t;
}

void dif(huge a, huge b) { 
    static shorty i; 
	static bool t;
	
	for(i = b[0]+1; i <= a[0]; ++i) b[i] = 0;
	for(i = 1, t = 0; i <= a[0]; ++i) 
		a[i] += (t=(a[i]-=b[i]+t)<0)*10;
	while(!a[a[0]] && a[0]) --a[0];
}

void product(huge a, huge b) {
	static shorty i, j; 
	static mini t;
	static huge c;
	
	c[0] = a[0]+b[0]+1;
	for(i = 1; i <= c[0]; ++i) c[i] = 0;
	for(i = 1; i <= a[0]; ++i) {
		for(j = 1, t = 0; j <= b[0]; ++j, t /= 10)
			c[i+j-1] = (t+=c[i+j-1]+a[i]*b[j])%10;
		if(t) c[i+j-1] = t;
	}	
	while(!c[c[0]]) --c[0];
	
	memcpy(a, c, sizeof(c));
}

void divide(huge a, huge b) { 
	static shorty i; 
	static huge c, r;
	
	r[0] = 1; c[0] = a[0];
	for(i = a[0]; i > 0; --i) {
		r[1] = a[i]; c[i] = 0;
		while(cmp(b, r) != 1) { 
			++c[i]; dif(r, b);
		}
		memmove(r+2, r+1, sizeof(int)*r[0]);
		if(r[r[0]+1]) ++r[0];
	}
	while(!c[c[0]] && c[0]) --c[0];
	
	memcpy(a, c, sizeof(c));
}

void factorial(huge a) {
	static huge b, c; 
	static shorty i;
	
	if(a[0] == 1 && a[1] == 0) {a[1] = 1; return;}
	memcpy(c, a, sizeof(huge));
	a[0] = b[0] = a[1] = b[1] = 1;
	while(cmp(b, c)) {
		++b[i=1];
		while(b[i] == 10) {
			b[i] = 0; ++b[++i];
			if(i > b[0]) b[0] = i;
		}
		product(a, b);
	}
}

char cmp(const huge a, const huge b) {
	if(a[0] < b[0]) return -1;
	if(a[0] > b[0]) return 1;
	
	static shorty i;
	for(i = a[0]; i && a[i] == b[i]; --i);
	
	if(i == 0) return 0;
    if(a[i] < b[i]) return -1;
    return 1;
}
/* Sfarsit Functi Numere Mari */