데이터 구조 과목 에 설 치 된 큰 정수 사 칙 연산

6857 단어 데이터 구조
작년 에 쓴 큰 정수 사 칙 연산 과목 을 지금 은 까맣게 잊 어 버 렸 는데, 다시 써 도 쓸 수 있 을 지 없 을 지 정말 슬 프 고 재촉 된다.
당시 에 선생님 은 진짜 변 태 를 구 하려 고 했 기 때문에 시스템 이 가지 고 있 는 스 택, 배열 로 저장 할 수 없 었 고 반드시 스스로 스 택 을 쓰 고 링크 로 큰 수 를 저장 해 야 했다.
main:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include"calculate.h"
#define INF 99999999
using namespace std;

const int MAX=10;

typedef struct stack{
	int *date;//    
	char ch;
	int mark;//mark      :  
	stack *next;
	stack(){
		next=NULL,mark=1;
	}
};

typedef struct head{
	stack *top;
	int size;
	head(){
		top=NULL,size=0;
	}
	void push(stack* &p);
	void Clear();
	void Pop();
};
head stack_dou,stack_ch;//       ,        .

void output(stack* &p){
	cout<date[0];
	if(p->date[l] != 0 && p->mark == -1)cout<date[l];
	for(int i=l-1;i>=1;--i)cout<date[i];
	cout<next=this->top;
	this->top=p;
	this->size++;
}

void head::Pop(){//      . 
	stack *p=this->top;
	this->top=this->top->next;
	this->size--;
	delete p;
}

void head::Clear(){//   . 
	while(this->top){
		stack *p=this->top;
		this->top=this->top->next;
		delete p;
	}
	this->size=0;
}

bool stack_dou_calculate(char s){//s     ,               . 
    if(stack_dou.size<2)return false;
	int *second=stack_dou.top->date,mark2=stack_dou.top->mark;
	stack_dou.top->date=NULL;stack_dou.Pop();
	int *first=stack_dou.top->date,mark1=stack_dou.top->mark;
	stack_dou.top->date=NULL;stack_dou.Pop();
	int *sum=new int[100];
	if(s == '+' && mark1*mark2 == 1 || 
	  (s == '-' && mark1*mark2 == -1))add(first,second,sum);//   
	if(s == '-' && mark1*mark2 == 1){//   
		if(cmp(first,second))sub(first,second,sum);
		else {sub(second,first,sum);mark1=-1*mark2;}
	}
	if(s == '+' && mark1*mark2 == -1){//   
		if(cmp(first,second))sub(first,second,sum);
		else {sub(second,first,sum);mark1=mark2;}
	}
	if(s == '*')mult(first,second,sum);//   
	if(s == '/')div(first,second,sum);//   
	stack *p=new stack;
	p->date=sum;
	p->mark=mark1;
	stack_dou.push(p);
	delete first;
	delete second;
	return true;
}

bool cmp(char a,char b){//     a,b    . 
	if(b == '+' || b == '-' || a== '*' || a == '/' || b == ')' || a == '(')return true;
	return false;
}

void calculate(string s){//     s. 
	string a;
	for(int i=0;idate=new int[100];trans(a,p->date);stack_dou.push(p);a.clear();}continue;}
 		if(isdigit(s[i]))a+=s[i];
		else if(isoperator(s[i])){
			if(a.size()){stack *p=new stack;p->date=new int[100];trans(a,p->date);stack_dou.push(p);a.clear();}
			while(stack_ch.top && cmp(stack_ch.top->ch,s[i])){
				if(stack_ch.top->ch != '('){
					if(!stack_dou_calculate(stack_ch.top->ch))break;
					stack_ch.Pop();
				}
    	        else {stack_ch.Pop();break;}
			}
			if(s[i] != ')'){stack *p=new stack;p->ch=s[i];stack_ch.push(p);}
		}
		else{cout<date=new int[100];trans(a,p->date);stack_dou.push(p);a.clear();}
	while(stack_ch.top){
		if(!stack_dou_calculate(stack_ch.top->ch))break;
		stack_ch.Pop();
	}
	if(stack_dou.size == 1 && stack_ch.size == 0)
	    output(stack_dou.top);
	else cout<
head:
#include
#include
using namespace std;

//******************************************************************************
const int Base=10000,seg=4;
//******************************************************************************

void trans(string ch,int *s){//          
	int i,k=1;
	int L=ch.size()-seg; 
	for(i=L;i>=0;i-=seg,k++){//        ,            .
		s[k]=ch[i]-'0';
		for(int j=i+1;j=Base){
			c=sum[i]/Base;
			sum[i]%=Base;
		}else c=0;
	}
    if(c>0){
    	sum[i]=c;
    	sum[0]=i;
    }
    else sum[0]=i-1;
}
//******************************************************************************

void sub(int *A,int *B,int *sum){//     
	int c=0;
	for(int i=B[0]+1;i<=A[0];++i)B[i]=0;
	for(int i=1;i<=A[0];++i){
		sum[i]=A[i]-B[i]+c;
		if(sum[i]<0){
			sum[i]+=Base;
			c=-1;
		}else c=0;
	}
	sum[0]=1;
	for(int i=A[0];i>=1;--i){
		if(sum[i]){
			sum[0]=i;
			break;
		}
	}
}
//******************************************************************************

void mult(int *A,int *B,int *sum){//      
	int i,j,k;
	int all=A[0]+B[0]-1;
	memset(sum,0,sizeof(int)*(all+3));
	for(i=1,k=1;i<=A[0];++i){
		k=i;
		if(A[i]){
			for(j=1;j<=B[0];++j,++k){
				sum[k]+=A[i]*B[j];
				if(sum[k]>=Base){
				   sum[k+1]+=sum[k]/Base;
				   sum[k]=sum[k]%Base;	
				}
			}
		}
	}
	while(sum[k]>=Base){
		sum[k+1]+=sum[k]/Base;
		sum[k]=sum[k++]%Base;
	}
	if(!sum[k])k--;
	sum[0]=k;
}
//******************************************************************************

//  a,b    
bool cmp(int *a,int *b){
	if(a[0]>b[0])return true;
	if(a[0]=1;--i){
		if(a[i]>b[i])return true;
		if(a[i]=1;--i,++j){
		if(a[t]>b[i])return j;
		if(a[t]=0;--i)sum[i]=0;
	for(int i=k,t=m;i>=1,t>=n;){
		int p=cmp(a,b,t);//a[t]-b[n]
		if(p<0 && t == n)break;
		if(p == 0){
			sum[i]++;
			for(int j=t;j>=t-n+1;--j)a[j]=0;
			t-=n;
			if(t1){
			sum[i]++;
			for(int j=t,q=n;j>=t-n+1;--j,--q)a[j]-=b[q];
			for(int j=t-n+1;j<=t;++j){
				if(a[j]<0){
					a[j]+=Base,a[j+1]--;
				}
			}
			int j;
			for(int j=t;j>=t-n+1;--j)if(a[j])break;
			if(jn){
			a[t-1]+=a[t]*Base;
			a[t]=0;
			--t;
			--i;
		}
		if(p == 1){
			int x=a[t]/(b[n]+1);
			sum[i]+=x;
			for(int j=t,q=n;q>=1;--q,--j)a[j]-=x*b[q];
			for(int j=t-n+1;j<=t;++j){
				while(a[j]<=-Base1000){a[j]+=Base1000,a[j+1]-=1000;}
				while(a[j]<=-Base100){a[j]+=Base100,a[j+1]-=100;}
				while(a[j]<=-Base10){a[j]+=Base10,a[j+1]-=10;}
				while(a[j]<=0){a[j]+=Base,a[j+1]-=1;}
			}
		}
	}
	if(sum[k] == 0)sum[0]=k-1;else sum[0]=k;
	/*int i;
	for(i=m;i>=1;--i)if(a[i])break;
	if(i == 0)copy(r,zero);
	else{
		r[0]=i;
		while(i >= 1)r[i]=a[i--];
	}*/
}

좋은 웹페이지 즐겨찾기