去年写的一个大整数四则运算课设,现在自己竟然忘得一干二净了，也不知道再次写还能不能写出来,真是悲催
当时老师要求真变态,不能用系统自带的栈，数组去存数，必须自己写个栈和用链表去存大数
main:
[cpp]view plaincopyprint?
#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
int l=p->date[0];
if(p->date[l] != 0 && p->mark == -1)cout
coutdate[l];
for(int i=l-1;i>=1;--i)coutdate[i];
cout
}
bool isoperator(char s){//判断运算符s是否符合条件.
if(s == '+' || s == '-' || s == '*' || s == '/' || s == '(' || s == ')')return true;
return false;
}
void head::push(stack* &p){//元素入栈.
p->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
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;i
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;}
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
}
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){
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
}
int main(){
string s;
cout
while(getline(cin,s)){//输入表达式s.
calculate(s);//计算表达式s.
stack_dou.Clear();//清空实数栈.
stack_ch.Clear();//清空字符栈.
cout
}
return 0;
}
/*
2+3*4+5
[***********][***********]2+[***********][**************]1
[***********][1**********]222*[***********][**************]
[***********][***********][***********][***********]1*[***********][***********]00000000
[***********][***********]-[***********]888+[**************]7/[1**********]22
[***********][***********]66/2222222
(2+3)*[***********][***********]000
1111-[***********]22222
1-2+3*6-(2+4)
5+6/9*7/2
*/
head:
[cpp]view plaincopyprint?
#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
s[k]=s[k]*10+ch[j]-'0';
}
}
i+=seg;
s[k]=0;
for(int j=0;j
s[k]=s[k]*10+ch[j]-'0';
}
if(s[k])s[0]=k;//s[0]储存该数组的位数.
else s[0]=k-1;
}
//******************************************************************************
void add(int *A,int *B,int *sum){//大整数相加
int la=max(A[0],B[0]),i,c=0;
for(int i=A[0]+1;i
for(int i=B[0]+1;i
for(i=1;i
sum[i]=A[i]+B[i]+c;
if(sum[i]>=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
for(int i=1;i
sum[i]=A[i]-B[i]+c;
if(sum[i]
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
k=i;
if(A[i]){
for(j=1;j
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]
for(int i=a[0];i>=1;--i){
if(a[i]>b[i])return true;
if(a[i]
}
return true;
}
//比较a从第t个位置开始和b的大小
int cmp(int *a,int *b,int t){
int i,j=1;
for(i=b[0];i>=1;--i,++j){
if(a[t]>b[i])return j;
if(a[t]
--t;
}
return 0;
}
void copy(int *a,int *b){
a[0]=b[0];
for(int i=1;i
}
int zero[]={1,0};
//sum=a/b,r=a%b
void div(int *a,int *b,int *sum/*,int *r*/){//大整数除法
int m=a[0],n=b[0];
int Base1000=Base*1000,Base100=Base*100,Base10=Base*10;
if(!cmp(a,b)){
/*copy(r,a),*/copy(sum,zero);
return;
}
int k=m-n+1;
for(int i=k;i>=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
if(p == 0){
sum[i]++;
for(int j=t;j>=t-n+1;--j)a[j]=0;
t-=n;
if(t
i-=n;
}
if(p>1){
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
if(a[j]
a[j]+=Base,a[j+1]--;
}
}
int j;
for(int j=t;j>=t-n+1;--j)if(a[j])break;
if(j
i-=(t-j);
t=j;
}
if(pn){
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
while(a[j]
while(a[j]
while(a[j]
while(a[j]
}
}
}
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--];
}*/
}