数据结构课设之大整数四则运算

去年写的一个大整数四则运算课设,现在自己竟然忘得一干二净了，也不知道再次写还能不能写出来,真是悲催

当时老师要求真变态,不能用系统自带的栈，数组去存数，必须自己写个栈和用链表去存大数

main:

[cpp] view plaincopyprint?

1. #include<iostream>  
2. #include<cstdio>  
3. #include<cstdlib>  
4. #include<cstring>  
5. #include<string>  
6. #include<algorithm>  
7. #include<queue>  
8. #include<map>  
9. #include<iomanip>  
10. #include<ctype.h>  
11. #include"calculate.h"  
12. #define INF 99999999  
13. using namespace std;  
14.   
15. const int MAX=10;  
16.   
17. typedef struct stack{  
18.     int *date;//存大数   
19.     char ch;  
20.     int mark;//mark用来标记符号:正负  
21.     stack *next;  
22.     stack(){  
23.         next=NULL,mark=1;  
24.     }  
25. };  
26.   
27. typedef struct head{  
28.     stack *top;  
29.     int size;  
30.     head(){  
31.         top=NULL,size=0;  
32.     }  
33.     void push(stack* &p);  
34.     void Clear();  
35.     void Pop();  
36. };  
37. head stack_dou,stack_ch;//一个用来存数字,一个用来存运算符.  
38.   
39. void output(stack* &p){  
40.     cout<<"结果是:";  
41.     int l=p->date[0];  
42.     if(p->date[l] != 0 && p->mark == -1)cout<<"-";  
43.     cout<<p->date[l];  
44.     for(int i=l-1;i>=1;--i)cout<<setfill('0')<<setw(4)<<p->date[i];  
45.     cout<<endl;  
46. }  
47.   
48. bool isoperator(char s){//判断运算符s是否符合条件.   
49.     if(s == '+' || s == '-' || s == '*' || s == '/' || s == '(' || s == ')')return true;  
50.     return false;  
51. }  
52.   
53. void head::push(stack* &p){//元素入栈.   
54.     p->next=this->top;  
55.     this->top=p;  
56.     this->size++;  
57. }  
58.   
59. void head::Pop(){//删除栈顶元素.   
60.     stack *p=this->top;  
61.     this->top=this->top->next;  
62.     this->size--;  
63.     delete p;  
64. }  
65.   
66. void head::Clear(){//清空栈.   
67.     while(this->top){  
68.         stack *p=this->top;  
69.         this->top=this->top->next;  
70.         delete p;  
71.     }  
72.     this->size=0;  
73. }  
74.   
75. bool stack_dou_calculate(char s){//s代表运算符,对实数栈的栈顶两个元素进行运算.   
76.     if(stack_dou.size<2)return false;  
77.     int *second=stack_dou.top->date,mark2=stack_dou.top->mark;  
78.     stack_dou.top->date=NULL;stack_dou.Pop();  
79.     int *first=stack_dou.top->date,mark1=stack_dou.top->mark;  
80.     stack_dou.top->date=NULL;stack_dou.Pop();  
81.     int *sum=new int[100];  
82.     if(s == '+' && mark1*mark2 == 1 ||   
83.       (s == '-' && mark1*mark2 == -1))add(first,second,sum);//相加   
84.     if(s == '-' && mark1*mark2 == 1){//相减   
85.         if(cmp(first,second))sub(first,second,sum);  
86.         else {sub(second,first,sum);mark1=-1*mark2;}  
87.     }  
88.     if(s == '+' && mark1*mark2 == -1){//相减   
89.         if(cmp(first,second))sub(first,second,sum);  
90.         else {sub(second,first,sum);mark1=mark2;}  
91.     }  
92.     if(s == '*')mult(first,second,sum);//相乘   
93.     if(s == '/')div(first,second,sum);//相除   
94.     stack *p=new stack;  
95.     p->date=sum;  
96.     p->mark=mark1;  
97.     stack_dou.push(p);  
98.     delete first;  
99.     delete second;  
100.     return true;  
101. }  
102.   
103. bool cmp(char a,char b){//比较运算符a,b的优先级.   
104.     if(b == '+' || b == '-' || a== '*' || a == '/' || b == ')' || a == '(')return true;  
105.     return false;  
106. }  
107.   
108. void calculate(string s){//计算表达式s.   
109.     string a;  
110.     for(int i=0;i<s.size();++i){  
111.         if(s[i] == ' '){if(a.size()){stack *p=new stack;p->date=new int[100];trans(a,p->date);stack_dou.push(p);a.clear();}continue;}  
112.         if(isdigit(s[i]))a+=s[i];  
113.         else if(isoperator(s[i])){  
114.             if(a.size()){stack *p=new stack;p->date=new int[100];trans(a,p->date);stack_dou.push(p);a.clear();}  
115.             while(stack_ch.top && cmp(stack_ch.top->ch,s[i])){  
116.                 if(stack_ch.top->ch != '('){  
117.                     if(!stack_dou_calculate(stack_ch.top->ch))break;  
118.                     stack_ch.Pop();  
119.                 }  
120.                 else {stack_ch.Pop();break;}  
121.             }  
122.             if(s[i] != ')'){stack *p=new stack;p->ch=s[i];stack_ch.push(p);}  
123.         }  
124.         else{cout<<"输入错误,请重输!\n";return;}  
125.     }  
126.     if(a.size()){stack *p=new stack;p->date=new int[100];trans(a,p->date);stack_dou.push(p);a.clear();}  
127.     while(stack_ch.top){  
128.         if(!stack_dou_calculate(stack_ch.top->ch))break;  
129.         stack_ch.Pop();  
130.     }  
131.     if(stack_dou.size == 1 && stack_ch.size == 0)  
132.         output(stack_dou.top);  
133.     else cout<<"输入错误,请重输!\n";  
134. }  
135.   
136. int main(){  
137.     string s;  
138.     cout<<"请输入表达式:";  
139.     while(getline(cin,s)){//输入表达式s.   
140.         calculate(s);//计算表达式s.   
141.         stack_dou.Clear();//清空实数栈.   
142.         stack_ch.Clear();//清空字符栈.  
143.         cout<<"请输入表达式:";   
144.     }  
145.     return 0;  
146. }  
147. /* 
148. 2+3*4+5 
149. 2222222222222222222222222222222222222+1111111111111111111111111111111111 
150. 22222222222222222222222222222222*444444444444444444444444444444444 
151. 1111111111111111111111111111111111111111111111111111111111111111111111111*10000000000000000000000000000000000000000000 
152. 999999999999999999999999999999999999-888888888888888888888+7777777777777777/2222222222222 
153. 66666666666666666666666666666666666666/2222222 
154. (2+3)*100000000000000000000000000000000000000 
155. 1111-22222222222222222222222 
156. 1-2+3*6-(2+4) 
157. 5+6/9*7/2 
158. */  

head:

[cpp] view plaincopyprint?

1. #include<cstring>  
2. #include<string>  
3. using namespace std;  
4.   
5. //******************************************************************************  
6. const int Base=10000,seg=4;  
7. //******************************************************************************  
8.   
9. void trans(string ch,int *s){//将字符串转化为数字   
10.     int i,k=1;  
11.     int L=ch.size()-seg;   
12.     for(i=L;i>=0;i-=seg,k++){//从字符串后面开始,依次四位四位存入整型数组.  
13.         s[k]=ch[i]-'0';  
14.         for(int j=i+1;j<i+seg;++j){  
15.             s[k]=s[k]*10+ch[j]-'0';  
16.         }  
17.     }  
18.     i+=seg;  
19.     s[k]=0;  
20.     for(int j=0;j<i;++j){  
21.         s[k]=s[k]*10+ch[j]-'0';  
22.     }  
23.     if(s[k])s[0]=k;//s[0]储存该数组的位数.   
24.     else s[0]=k-1;  
25. }  
26. //******************************************************************************  
27.   
28. void add(int *A,int *B,int *sum){//大整数相加   
29.     int la=max(A[0],B[0]),i,c=0;  
30.     for(int i=A[0]+1;i<=la;++i)A[i]=0;  
31.     for(int i=B[0]+1;i<=la;++i)B[i]=0;  
32.     for(i=1;i<=la;++i){  
33.         sum[i]=A[i]+B[i]+c;  
34.         if(sum[i]>=Base){  
35.             c=sum[i]/Base;  
36.             sum[i]%=Base;  
37.         }else c=0;  
38.     }  
39.     if(c>0){  
40.         sum[i]=c;  
41.         sum[0]=i;  
42.     }  
43.     else sum[0]=i-1;  
44. }  
45. //******************************************************************************  
46.   
47. void sub(int *A,int *B,int *sum){//大数相减   
48.     int c=0;  
49.     for(int i=B[0]+1;i<=A[0];++i)B[i]=0;  
50.     for(int i=1;i<=A[0];++i){  
51.         sum[i]=A[i]-B[i]+c;  
52.         if(sum[i]<0){  
53.             sum[i]+=Base;  
54.             c=-1;  
55.         }else c=0;  
56.     }  
57.     sum[0]=1;  
58.     for(int i=A[0];i>=1;--i){  
59.         if(sum[i]){  
60.             sum[0]=i;  
61.             break;  
62.         }  
63.     }  
64. }  
65. //******************************************************************************  
66.   
67. void mult(int *A,int *B,int *sum){//大整数相乘   
68.     int i,j,k;  
69.     int all=A[0]+B[0]-1;  
70.     memset(sum,0,sizeof(int)*(all+3));  
71.     for(i=1,k=1;i<=A[0];++i){  
72.         k=i;  
73.         if(A[i]){  
74.             for(j=1;j<=B[0];++j,++k){  
75.                 sum[k]+=A[i]*B[j];  
76.                 if(sum[k]>=Base){  
77.                    sum[k+1]+=sum[k]/Base;  
78.                    sum[k]=sum[k]%Base;    
79.                 }  
80.             }  
81.         }  
82.     }  
83.     while(sum[k]>=Base){  
84.         sum[k+1]+=sum[k]/Base;  
85.         sum[k]=sum[k++]%Base;  
86.     }  
87.     if(!sum[k])k--;  
88.     sum[0]=k;  
89. }  
90. //******************************************************************************  
91.   
92. //比较a,b的大小   
93. bool cmp(int *a,int *b){  
94.     if(a[0]>b[0])return true;  
95.     if(a[0]<b[0])return false;  
96.     for(int i=a[0];i>=1;--i){  
97.         if(a[i]>b[i])return true;  
98.         if(a[i]<b[i])return false;  
99.     }  
100.     return true;  
101. }  
102.   
103. //比较a从第t个位置开始和b的大小  
104. int cmp(int *a,int *b,int t){  
105.     int i,j=1;  
106.     for(i=b[0];i>=1;--i,++j){  
107.         if(a[t]>b[i])return j;  
108.         if(a[t]<b[i])return -1;  
109.         --t;  
110.     }  
111.     return 0;  
112. }   
113.   
114. void copy(int *a,int *b){  
115.     a[0]=b[0];  
116.     for(int i=1;i<=a[0];++i)a[i]=b[i];  
117. }  
118.   
119. int zero[]={1,0};  
120.   
121. //sum=a/b,r=a%b  
122. void div(int *a,int *b,int *sum/*,int *r*/){//大整数除法   
123.     int m=a[0],n=b[0];  
124.     int Base1000=Base*1000,Base100=Base*100,Base10=Base*10;  
125.     if(!cmp(a,b)){  
126.         /*copy(r,a),*/copy(sum,zero);  
127.         return;  
128.     }  
129.     int k=m-n+1;  
130.     for(int i=k;i>=0;--i)sum[i]=0;  
131.     for(int i=k,t=m;i>=1,t>=n;){  
132.         int p=cmp(a,b,t);//a[t]-b[n]  
133.         if(p<0 && t == n)break;  
134.         if(p == 0){  
135.             sum[i]++;  
136.             for(int j=t;j>=t-n+1;--j)a[j]=0;  
137.             t-=n;  
138.             if(t<n)break;  
139.             i-=n;  
140.         }  
141.         if(p>1){  
142.             sum[i]++;  
143.             for(int j=t,q=n;j>=t-n+1;--j,--q)a[j]-=b[q];  
144.             for(int j=t-n+1;j<=t;++j){  
145.                 if(a[j]<0){  
146.                     a[j]+=Base,a[j+1]--;  
147.                 }  
148.             }  
149.             int j;  
150.             for(int j=t;j>=t-n+1;--j)if(a[j])break;  
151.             if(j<n)break;  
152.             i-=(t-j);  
153.             t=j;  
154.         }  
155.         if(p<0 && t>n){  
156.             a[t-1]+=a[t]*Base;  
157.             a[t]=0;  
158.             --t;  
159.             --i;  
160.         }  
161.         if(p == 1){  
162.             int x=a[t]/(b[n]+1);  
163.             sum[i]+=x;  
164.             for(int j=t,q=n;q>=1;--q,--j)a[j]-=x*b[q];  
165.             for(int j=t-n+1;j<=t;++j){  
166.                 while(a[j]<=-Base1000){a[j]+=Base1000,a[j+1]-=1000;}  
167.                 while(a[j]<=-Base100){a[j]+=Base100,a[j+1]-=100;}  
168.                 while(a[j]<=-Base10){a[j]+=Base10,a[j+1]-=10;}  
169.                 while(a[j]<=0){a[j]+=Base,a[j+1]-=1;}  
170.             }  
171.         }  
172.     }  
173.     if(sum[k] == 0)sum[0]=k-1;else sum[0]=k;  
174.     /*int i; 
175.     for(i=m;i>=1;--i)if(a[i])break; 
176.     if(i == 0)copy(r,zero); 
177.     else{ 
178.         r[0]=i; 
179.         while(i >= 1)r[i]=a[i--]; 
180.     }*/  
181. }