Object-C 栈的应用实现两个大数相加

• 对于两个非常大的数，如1233333333333333333333333333+9090909090909090909090090909909090909090909090是无法直接相加的。因为已经超过了整型变量的限制可以使用下面代码获得基本类型在运行平台的存储范围：

NSLog(@"72----------byte:%ld  max :%ld min:%ld",sizeof(NSInteger),NSIntegerMax,NSIntegerMin);

• 为了解决这个问题，可以将这种非常大的数据看成一串字符串，将这个字符串分别存入两个栈中，然后从栈中弹出数，进行加法操作。

• 基本思想：

• 读入第一个数的数字num1，并将这些数字存到一个栈中（假设为Stack1）；
• 读入第二个数的数字num2，并将这些数字存到一个栈中（假设为Stack2）；
• 定义一个用来保存进位的变量plus = 0;
• while(至少一个栈不空)：
  1.从每一个非空的栈弹出一个数，将这两个数字与plus相加；
  2.将个位数存入结果栈中（resultStack）;
  3.判断是否发生进位（判断num1 + num2 > 9），如果发生进位，将进位存入plus中，否则将plus 恢复为0；
• 如果进位不为0，将其存入结果栈中；
• 从结果栈弹出结果返回即可；

• 下图给出应用这种算法的一个示例。示例数为592与3748

  
  image.png

image.png

• 核心代码如下：

#import "AddLargeNumber.h"
#import "Stack.h"

@interface AddLargeNumber()
@property(nonatomic,strong) Stack* operatorStack1;
@property(nonatomic,strong) Stack* operatorStack2;
@property(nonatomic,strong) Stack* resultStack;

@end

@implementation AddLargeNumber


-(NSString*) addLargeNumber:(NSString*) number1 number2:(NSString*) number2{
    NSMutableString* result = [[NSMutableString alloc] init];
    if (!self.operatorStack1) {
        self.operatorStack1 = [[Stack alloc] initWithSize:[number1 length]];
    }
    if (!self.operatorStack2) {
        self.operatorStack2 = [[Stack alloc] initWithSize:[number2 length]];
    }
    
    if (!self.resultStack) {
        self.resultStack = [[Stack alloc] initWithSize:[number1 length] + [number2 length]];
    }
    
    for(int i = 0;i < [number1 length]; i++){
        NSString *ch = [number1 substringWithRange:NSMakeRange(i,1)];
        [self.operatorStack1 push:ch];
    }
    
    for(int i = 0;i < [number2 length]; i++){
        NSString *ch = [number2 substringWithRange:NSMakeRange(i,1)];
        [self.operatorStack2 push:ch];
    }
    [self.operatorStack1 test];
    [self.operatorStack2 test];
    NSInteger carry = 0;
    while(![self.operatorStack1 isEmpty] || ![self.operatorStack2 isEmpty]){
        NSInteger opt1 = 0;
        NSInteger opt2 = 0;
        if(![self.operatorStack1 isEmpty]){
            opt1 = [(NSString*)[self.operatorStack1 pop] intValue] ;
        }
        if(![self.operatorStack2 isEmpty]){
            opt2 = [(NSString*)[self.operatorStack2 pop] intValue] ;
        }
        NSInteger tmpResult = opt1 + opt2 + carry;
        if (tmpResult > 9) {  //发生进位
            carry = 1;
            NSInteger geWei = tmpResult - 10;
            [self.resultStack push:[NSString stringWithFormat:@"%ld",geWei]];
        }else{
            carry = 0;
            [self.resultStack push:[NSString stringWithFormat:@"%ld",tmpResult]];
        }
        [self.resultStack test];
    }

    while (![self.resultStack isEmpty]) {
        NSString* tmp = (NSString*)[self.resultStack pop];
        [result appendString:tmp];
    }
    return [result copy];
    
}

@end

• 运行结果：

  
  image.png

书籍参考 《数据结构C++版》