經典算法11：任意長度整數加法

    #include


#include   
#include   

#define STACK_INIT_SIZE 20  
#define STACKINCREMENT 10  
/*定義堆棧*/  
typedef  char ElemType;  
typedef struct{  
   ElemType *base;  
   ElemType *top;  
   int stacksize;  
}sqStack;  
/*初始化棧*/  
void initStack(sqStack *s)  
{  
    /*內存中開辟一段連續空間作為棧空間，首地址賦值給s->base*/  
    s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));  
    if(!s->base) exit(0);                    /*分配空間失敗*/  
    s->top = s->base;                    /*最開始，棧頂就是棧底*/  
    s->stacksize = STACK_INIT_SIZE;        /*最大容量為STACK_INIT_SIZE */  
}  
/*入棧操作，將e壓入棧中*/  
void Push(sqStack *s, ElemType e){  
    if(s->top - s->base >= s->stacksize){  
    /*棧滿，追加空間*/  
    s->base = (ElemType *)realloc(s->base, (s->stacksize +  
    STACKINCREMENT)*sizeof(ElemType));  
    if(!s->base) exit(0);                                /*存儲分配失敗*/  
    s->top = s->base + s->stacksize;  
    s->stacksize = s->stacksize + STACKINCREMENT;        /*設置棧的最大容量*/  
    }  
    *(s->top) = e;                                    /*放入數據*/  
        s->top++;  
}  
/*出棧操作，用e將棧頂元素返回*/  
void Pop(sqStack *s , ElemType *e){  
    if(s->top == s->base) return;  
    *e = *--(s->top);  
}  

/*計算堆棧s當前的長度*/  
int StackLen(sqStack s){  
    return (s.top - s.base) ;  
}  

void ADD(sqStack *s1,sqStack *s2,sqStack *s3)  
{  
 char a1,a2,a3,c=0;                 /*a1,a2分別存放從堆棧s1,s2中取出的（數據）元素， 
a3=a1+a2,c中存放進位*/  
    while(StackLen(*s1)!=0 && StackLen(*s2)!=0)  
    {  
         Pop(s1,&a1);                    /*取出s1棧的棧頂元素給a1*/  
         Pop(s2,&a2);                    /*取出s2棧的棧頂元素給a2*/  
         a3 = (a1-48) + (a2-48) + c + 48;        /*相加*/  
         if(a3>'9')  
         {  
               a3 = a3 - '9' + 47;            /*產生進位的情況*/  
               c = 1;  
          }  
          else  
              c = 0;                    /*不產生進位*/  
         Push(s3,a3);                    /*將結果入棧s3*/  
     }  
     if(StackLen(*s1)!=0)                    /*棧s1不為空的情況*/  
     {  
        while(StackLen(*s1)!=0)  
        {  
           Pop(s1,&a1);                    /*取出s1棧的棧頂元素給a1*/  
           a3 = a1 + c ;                    /*與進位標志c相加*/  
           if(a3>'9')  
           {  
               a3 = a3 - '9' + 47;            /*產生進位的情況*/  
               c = 1;  
           }  
          else  
              c = 0;                    /*不產生進位*/  
           Push(s3,a3);                    /*將結果入棧s3*/  
        }  
     }  
     else if(StackLen(*s2)!=0)                /*棧s1不為空的情況*/  
     {  
        while(StackLen(*s2)!=0)  
        {  
           Pop(s2,&a2);                    /*取出s1棧的棧頂元素給a1*/  
           a3 = a2 + c;                    /*與進位標志c相加*/  
           if(a3>'9')  
           {  
                a3 = a3 - '9' + 47;            /*產生進位的情況*/  
               c = 1;  
           }  
          else  
              c = 0;                    /*不產生進位*/  
           Push(s3,a3);                    /*棧s1不為空的情況*/  
        }  
     }  
     if(c==1)  
        Push(s3,'1');                    /*如果最后有進位，將字符’1’入棧s3*/  
}  

int main()  
{  
    char e;  
    sqStack s1,s2,s3;  
    initStack(&s1);                            /*初始化堆棧s1，存放加數*/  
    initStack(&s2);                            /*初始化堆棧s2，存放加數*/  
    initStack(&s3);                            /*初始化堆棧s3，存放結果*/  
    printf("Please input the first integer\n");        /*輸入第一個任意長整數，按”#”結尾*/  
    scanf("%c",&e);  
    while(e!='#')  
    {  
       Push(&s1,e);                            /*將加數（字符串）入棧s1*/  
       scanf("%c",&e);  
    }  
    getchar();                                /*接收回車符*/  
    printf("Please input the second integer\n");        /*輸入第二個任意長整數，按”#”結尾*/  
    scanf("%c",&e);  
    while(e!='#')  
    {  
       Push(&s2,e);                            /*將加數（字符串）入棧s2*/  
       scanf("%c",&e);  
    }  
    ADD(&s1,&s2,&s3);                        /*加法運算，將結果存放在s3中*/  
    printf("The result is\n");  
    while(StackLen(s3)!=0)                    /*輸出結果，打印在屏幕上*/  
    {  
        Pop(&s3,&e);  
        printf("%c",e);  
    }  
    return 0;  </pre>