範例程式碼 uva288

//uva288
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#define MYDIG	100

int lastchar = -1;
struct longnum {
	int *n;
	int sign;
	int msd;
};

typedef struct longnum LNUM;
char runops[128] = {0};
char op = 0;
LNUM num[128], mytmp, myexp;
int sp = 0;

void showans() {
	LNUM* a = num;
	int k;
	char dump[4000], *p = dump;
	int i, len;
	if(a -> sign == -1)p += sprintf(p, "-");
	p += sprintf(p, "%d", a -> n[a -> msd-1]);
	for(k = a -> msd-2; k >= 0; --k)
		p += sprintf(p, "%02d", a -> n[k]);
	len = p - dump;
	
	for(i = 0; len > 75; len -= 75, i += 75)
		printf("%.75s\\\\\n", dump + i);
	printf("%s", dump + i);
	putchar('\n');
	free(a -> n);
}

void domul(LNUM *a, LNUM *b){
	if(a -> msd == 1 && a -> n[0] == 0) return;
	if(b -> msd == 1 && b -> n[0] == 0) {
		a -> msd = 1;
		a -> sign = 1;
		a -> n[0] = 0;
		return;
	}
	if(b -> msd == 1 && b -> n[0] == 1) return;
	LNUM *t = &mytmp;
	LNUM *c, *d;
	int i, k, j;
	int newsign = a -> sign*b -> sign;
	if(a -> msd > b -> msd) {
		c = a;
		d = b;
	}
	else {
		c = b;
		d = a;
	}
	int *tn = (int*)malloc(sizeof(int) * (a -> msd + b -> msd));
	int cy, sum;
	for(i = cy = 0; i < d -> msd - 1; ++i) {
		for(sum = cy, k = 0; k <= i; k++)
			sum = sum + c -> n[i - k] * d -> n[k];
		tn[i] = sum % MYDIG;
		cy = sum / MYDIG;
	}
	for(; i < c -> msd; ++i) {
		for(sum = cy, k = 0; k < d -> msd; k++)
			sum = sum + c -> n[i - k] * d -> n[k];
		tn[i] = sum % MYDIG;
		cy = sum / MYDIG;
	}
	for(j = 1; i < c -> msd + d -> msd - 1; ++i, ++j) {
		for(sum = cy, k = j; k < d -> msd; k++)
			sum = sum + c -> n[i - k] * d -> n[k];
		tn[i] = sum % MYDIG;
		cy = sum / MYDIG;
	}
	if(cy > 0) tn[i++] = cy;
	a -> msd = i;
	free(a -> n);
	a -> n = tn;
	a -> sign = newsign;
}

void doadd(LNUM *a, LNUM *b) {
	LNUM *c;
	int min, max;
	if(a -> msd > b -> msd) {
		c = a;
		max = a -> msd;
		min = b -> msd;
	}
	else {
		c = b;
		max = b -> msd;
		min = a -> msd;
	}
	int *tn = (int*)malloc(sizeof(int) * (max + 1));
	int i, cy, sum;
	for(cy = i = 0; i < min; ++i){
		sum = cy + a -> n[i] + b -> n[i];
		tn[i] = sum % MYDIG;
		cy = sum / MYDIG;
	}
	for(; i < max; ++i){
		sum = cy + c -> n[i];
		tn[i] = sum % MYDIG;
		cy = sum / MYDIG;
	}
	if(cy > 0) tn[i++] = cy;
	a -> msd = i;
	free(a -> n);
	a -> n = tn;
}

void doexp(LNUM *a, LNUM *b){
	if(a -> msd == 1 && a -> n[0] == 1)
		return;
	if(b -> msd == 1 && b -> n[0] == 0) {
		a -> msd = 1;
		a -> sign = 1;
		a -> n[0] = 1;
		return;
	}
	if(b -> msd == 1 && b -> n[0] == 1)
		return;
#define MYEXPSHIFT 16
#define MYEXPMASK 0xffff
	unsigned long v[100];
	int i, j, vlen = 0,  sum,  cy;
	for(i = 0; i < 100; ++i) v[i] = 0;
	for(i = b -> msd - 1; i >= 0;--i) {
		for(sum = b -> n[i], cy = j = 0; j <= vlen; j++){
			sum += v[j] * MYDIG + cy;
			v[j] = sum & MYEXPMASK;
			cy = sum >> MYEXPSHIFT;
			sum = 0;
		}
		if(cy){
			v[j++] = cy;
			vlen++;
		}
	}
	int *tn = (int*)malloc(sizeof(int) * 1);
	LNUM*e = &myexp;
	e -> n = a -> n;
	e -> sign = a -> sign;
	e -> msd = a -> msd;
	a -> sign = 1;
	a -> msd = 1;
	a -> n = tn;
	a -> n[0] = 1;
	for(i = 0; i <= vlen; ++i) {
		for(j = 0; j < 16; ++j) {
			if((v[i] & 1) == 1) domul(a, e);
			v[i] >>= 1;
			if(i == vlen && v[i] == 0) break;
			domul(e, e);
		}
	}
}

void dosub(LNUM *a, LNUM *b){
	LNUM *c, *d;
	int i, flag;
	if(a -> msd > b -> msd) flag = 1;
	else if(a -> msd < b -> msd) flag = 0;
	else {
		for(i = a -> msd-1; i >= 0 && a -> n[i] == b -> n[i]; i--);
		if(i < 0) {
			a -> n[0] = 0;
			a -> sign = 1;
			a -> msd = 1;
			return;
		}
		flag = a -> n[i] > b -> n[i] ? 1 : 0;
	}
	if(flag) c = a, d = b;
	else c = b, d = a;
	
	int max = c -> msd;
	int cy, sum;
	int *tn = (int*)malloc(sizeof(int) * max);
	for(cy = i = 0; i < max; ++i){
		if(i < d -> msd)
		  sum = c -> n[i] - d -> n[i] - cy;
		else
		  sum = c -> n[i] - cy;
		if(sum < 0) {
		  sum = sum + MYDIG;
		  cy = 1;
		}
		else cy = 0;
		tn[i] = sum;
	}
	for(i--; i > 0 && tn[i] == 0; --i);
	a -> msd = i + 1;
	if(flag == 0)
		a -> sign = c -> sign;
	free(a -> n);
	a -> n = tn;
}

void docal(){
	LNUM*a = num + sp - 2;
	LNUM*b = num + sp - 1;
	char opcode = runops[--op];
	switch(opcode) {
	case '+':
		if(a -> sign == b -> sign) doadd(a, b);
		else dosub(a, b);
		--sp;
		break;
	case '-':
		b -> sign *= -1;
		if(a -> sign == b -> sign) doadd(a, b);
		else dosub(a, b);
		--sp;
		break;
	case '*':
		domul(a, b);
		--sp;
		break;
	case '^':
		doexp(a, b);
		--sp;
		break;
	}
}
int checkop(){
	char flag = lastchar;
	char last;
	if(lastchar == 0 || lastchar == '\n' || lastchar == EOF) flag='$';
	else {
		char lastchar2 = getchar();
		if(lastchar == '*' && lastchar2 == '*'){
			flag='^';
			lastchar = getchar();
		}
		else lastchar = lastchar2;
	}
	while(op > 0) {
		last = runops[op-1];
		if(flag == '+' || flag == '-') {
			docal();
			continue;
		}
		else if(flag == '*') {
			if(last == '^' || last == '*') {
				docal();
				continue;
			}
		}
		else if(flag == '^')
			break;
		else{
			docal();
			continue;
		}
		break;
	}
	runops[op++] = flag;
	return flag == '$' ? 0 : 1;
}			
int checkexp(){
	for(;;){
		if(lastchar == EOF) return 1;
		if('0' <= lastchar && lastchar <= '9' || lastchar == '-' || lastchar == '+') return 0;
		lastchar = getchar();
	}
}
void loadlnum(){
	int i;
	char buf[1004];
	char *p, *s;
	LNUM *a = num + sp;
	++sp;
	int mysign = 1;
	if(lastchar == '-') {
		mysign = -1;
		lastchar = getchar();
	}
	else if(lastchar == '+') {
		mysign = 1;
		lastchar = getchar();
	}
	for(s = buf; '0' <= lastchar && lastchar <= '9'; ++s){
		*s = lastchar;
		lastchar = getchar();
	}
	char *t = buf;
	while(*t == '0') t++;
	if(t == s) t--;
	a -> n = (int*)malloc(sizeof(int) * ((s - t + 2) >> 1));
	for(i = 0, s--, p = t; s >= p; s -= 2, ++i)
		a -> n[i] = *s - '0' + (s - p - 1 >= 0 ? (*(s-1) - '0') * 10 : 0);
	if(i == 1 && a -> n[0] == 0) mysign = 1;
	a -> sign = mysign;
	a -> msd = i;
}

int main(void) {
	lastchar = getchar();
	int i;
	for(i = 0; ; ++i) {
		for(op = sp = 0;;) {
			loadlnum();
			if(checkop() == 0) break;
		}
		if(i)
			printf("\n");
		showans();
		if(checkexp() == 1) break;
	}
	return 0;
}