栈

如何理解”栈“

关于”栈“有一个非常贴切的例子，就是一摞叠在一起的盘子。平时放盘子的时候，都是从下往上一个一个放；取的时候，是从上往下一个一个地依次取，不能从中间任意抽出。后进者先出，先进者后出，这就是典型的”栈“结构。

从栈的操作特性上来看，栈是一种”操作受限“的线性表，只允许在一端插入和删除数据。
从功能上来说，数组或链表确实可以替代栈，但是特定的数据结构是对特定场景的抽象，而且，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错。
当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，这时就应该首选”栈“这种数据结构。

栈的实现

@interface DMStack<ObjectType> : NSObject

// 入栈操作
- (void)push:(ObjectType)aObject;

// 出栈操作
- (ObjectType)pop;

- (BOOL)isEmpty;

@end

@interface DMStack ()

@property (nonatomic, strong) NSMutableArray *mArray;

@end

@implementation DMStack

// 入栈操作
- (void)push:(id)aObject
{
    [self.mArray addObject:aObject];
}

// 出栈操作
- (id)pop
{
    id tmpObject = nil;
    if ([self.mArray count] > 0) {
        tmpObject = [self.mArray lastObject];
        [self.mArray removeLastObject];
    }
    return tmpObject;
}

- (BOOL)isEmpty
{
    BOOL bFlag = NO;
    if ([self.mArray count] == 0) {
        bFlag = YES;
    }
    return bFlag;
}

#pragma mark - getter and setter
- (NSMutableArray *)mArray
{
    if (_mArray == nil) {
        _mArray = [[NSMutableArray alloc] init];
    }
    return _mArray;
}

@end

栈在表达式求值中的应用

表达式求值通过两个栈来实现。其中一个保存操作数的栈，另一个是保存运算符的栈。从左向右遍历表达式，当遇到数字，就直接压入操作数栈；当遇到运算符时，做如下处理
如果运算符栈为空，就直接压入运算符栈；如果运算符栈不为空，就与运算符栈的栈顶元素进行比较。如果比运算符栈顶元素的优先级高，就将当前运算符压入运算符栈；如果比运算符栈顶元素的优先级低或者相等，从运算符栈中取栈顶运算符，从操作数栈的栈顶取2个操作数，然后进行计算，再把计算结果压入操作数栈，继续做运算符的处理，直至将运算符压入运算符栈。
表达式遍历完之后，取出一个运算符，取2个操作数，再把计算结果压入操作数栈，直至运算符栈为空，操作数栈中的值就为表达式的结果。
表达式3 + 5 * 8 - 6 这个表达式的计算过程如下

代码实现如下

@interface DMStackDemo ()

@end

@implementation DMStackDemo
- (void)test 
{
    NSString *aStr = @"3 + 5 * 8 - 6";
    [self demo:aStr];
    {
        NSString *bStr = @"3 + 5 - 8 * 6";
        [self demo:bStr];
    }
    
    {
        NSString *bStr = @"3 * 5 - 8 + 6 / 3";
        [self demo:bStr];
    }
}

- (void)demo:(NSString *)aStr
{
    NSArray *oneArray = [aStr componentsSeparatedByString:@" "];
    
    // 操作数栈
    DMStack<NSString *> *numberStack = [[DMStack<NSString *> alloc] init];
    // 操作符栈
    DMStack<NSString *> *operatorStack = [[DMStack<NSString *> alloc] init];
    for (NSString *tmpStr in oneArray) {
        if ([self isOperator:tmpStr]) {
            // 是操作符时
            BOOL bFlag = YES;
            while (bFlag) {
                if ([operatorStack isEmpty]) {
                    // 操作符栈为空时，压入操作符栈
                    [operatorStack push:tmpStr];
                    bFlag = NO;
                } else {
                    // 取出操作符栈顶元素
                    NSString *curOperatorStr = [operatorStack pop];
                    // 跟操作符栈顶元素比较
                    if ([self operatorPriority:curOperatorStr] >= [self operatorPriority:tmpStr]) {
                        // 栈顶元素优先级高时，取操作数计算
                        NSString *oneStr = [numberStack pop];
                        NSString *twoStr = [numberStack pop];
                        NSString *resultStr = [self calcuteOne:oneStr two:twoStr operator:curOperatorStr];
                        
                        // 将计算结果压入操作数栈
                        [numberStack push:resultStr];
                    } else {
                        // 栈顶元素优先级高时，压入操作符栈
                        [operatorStack push:curOperatorStr];
                        [operatorStack push:tmpStr];
                        bFlag = NO;
                    }
                }
            }
            
        } else {
            // 是操作数时，压入操作数栈
            [numberStack push:tmpStr];
        }
    }
    
    // 当操作符栈不为空时，取操作数计算
    while ([operatorStack isEmpty] == NO) {
        NSString *curOperatorStr = [operatorStack pop];
        NSString *oneStr = [numberStack pop];
        NSString *twoStr = [numberStack pop];
        NSString *resultStr = [self calcuteOne:oneStr two:twoStr operator:curOperatorStr];
        // 将计算结果压入操作数栈
        [numberStack push:resultStr];
    }
    
    NSString *resultStr = [numberStack pop];
    NSLog(@"表达式%@结果为：%@",aStr, resultStr);
}

- (BOOL)isOperator:(NSString *)str
{
    BOOL bFlag = NO;
    if ([str isEqualToString:@"+"] ||
        [str isEqualToString:@"-"] ||
        [str isEqualToString:@"*"] ||
        [str isEqualToString:@"/"]) {
        bFlag = YES;
    }
    return bFlag;
}

// 操作符优先级
- (NSInteger)operatorPriority:(NSString *)operatorStr
{
    NSInteger curPriority = 0;
    if ([operatorStr isEqualToString:@"+"] ||
        [operatorStr isEqualToString:@"-"]) {
        curPriority = 1;
    } else if ([operatorStr isEqualToString:@"*"] ||
               [operatorStr isEqualToString:@"/"]) {
        curPriority = 2;
    }
    return curPriority;
}

- (NSString *)calcuteOne:(NSString *)oneStr two:(NSString *)twoStr operator:(NSString *)operatorStr
{
    NSString *resultStr = nil;
    if ([operatorStr isEqualToString:@"+"]) {
        NSInteger resultValue = [oneStr integerValue] + [twoStr integerValue];
        NSNumber *resultNum = [NSNumber numberWithInteger:resultValue];
        resultStr = [NSString stringWithFormat:@"%@", resultNum];
    } else if ([operatorStr isEqualToString:@"-"]) {
        NSInteger resultValue = [twoStr integerValue] - [oneStr integerValue];
        NSNumber *resultNum = [NSNumber numberWithInteger:resultValue];
        resultStr = [NSString stringWithFormat:@"%@", resultNum];
    } else if ([operatorStr isEqualToString:@"*"]) {
        NSInteger resultValue = [oneStr integerValue] * [twoStr integerValue];
        NSNumber *resultNum = [NSNumber numberWithInteger:resultValue];
        resultStr = [NSString stringWithFormat:@"%@", resultNum];
    } else if ([operatorStr isEqualToString:@"/"]) {
        NSInteger resultValue = [twoStr integerValue] / [oneStr integerValue];
        NSNumber *resultNum = [NSNumber numberWithInteger:resultValue];
        resultStr = [NSString stringWithFormat:@"%@", resultNum];
    }
    return resultStr;
}

@end