【OJ】大数减法（使用栈的简单例子）

朱雀 2024-04-19 16:23 42阅读 0赞

## 1536: 大数减法 ##

### 题目描述 ###

求两个不超过200位的非负整数的差。

### 输入 ###

有两行，每行是一个不超过200位的非负整数，没有多余的前导0。

### 输出 ###

一行，即相减后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。

### 样例输入 ###

88888888888888888888
    33333333333333333333

### 样例输出 ###

55555555555555555555

### 解题代码 ###

大数运算也同样是单纯地运算，小学的时候学过那种运算。

因为每次进行减法操作其实都只是对最后一位进行的（已经生成结果的不算最后一位的话），并且输入输出都非常符合栈的特点（先进后出）。

比如说输入 `123456` 减去 `5648` ，首先进行的应该是最后一位，也就是 `6` 减去 `8`。如果以栈来存储的话，输入的是123456，则栈top就是6，同样另外一个栈就是8。  
所以减法操作在这里就是最后一个进入容器的数字进行的减法，所以可以考虑使用`栈`。

另外需要考虑为负数这个问题，等等。

#include <iostream>
    #include <stack>
    #include <cstring>
    using namespace std;
    /** * 获得某个字符串的长度 */
    int length(char str[])
    { 
        int i=0;
        while(str[i]!='\0') i++;
        return i;
    }
    
    /** * 比较两个字符串对应的整数，谁大 * 因为是大数，所以不能使用已经提供的函数 */
    int bigger(char str1[],char str2[])
    { 
       int length1 = length(str1);
       int length2 = length(str2);
       if(length1!=length2) return length1>length2;
       int i;
    
       for(i=0; i<length1; i++)
       { 
           if(str1[i]!=str2[i]) { 
                return str1[i] > str2[i];
           }
       }
       return -1;
    }
    
    // written by Smileyan 多谢关注
    int main()
    { 
        char str1[250],str2[250];
        stack<int> stack1,stack2,stack3;
        int i;
        cin>>str1>>str2;
    
        // 用来记录最终结果是不是负数
        bool neg = false;
        if(bigger(str1,str2) == false)
        { 
            neg = true;
            char temp[250];
            strcpy(temp,str1);
            strcpy(str1,str2);
            strcpy(str2,temp);
        }
    
        // 入栈
        for(i=0; str1[i]!='\0'; i++)
        { 
            stack1.push(str1[i]-'0');
        }
        for(i=0; str2[i]!='\0'; i++)
        { 
            stack2.push(str2[i]-'0');
        }
    
        int result;
    
        // 如果是负数，则为1
        bool flag=false;
        while(stack1.empty()==false&&stack2.empty()==false)
        { 
            int num1 = stack1.top()-flag;
            stack1.pop();
            int num2 = stack2.top();
            stack2.pop();
            result = num1-num2;
            flag = result<0;
    
            // 如果这一位进行减法为负数，需要往上借一位
            if(flag)    { 
                result += 10;
            }
            stack3.push(result);
        }
    
        if(neg == true) cout<<"-";
        
        while(stack3.empty()==false)
        { 
            int num=stack3.top();
            stack3.pop();
            cout<<num;
        }
        cout<<endl;
        return 0;
    }

### 总结 ###

并不难，如果回想一下小学学过的，列两个数然后进行减法操作的过程的话。

> Smileyan  
> 2019年9月19日 21:21