ios 栈来解决平衡符号的问题

前言

之前去面试遇到一个面试题，意思大概是这样的：检测括号是否成对，每一个右花括号)、右方括号]、右大括号}，必然要对应一个相应的左花括(号、左方括号[以及左大括号{。也就是说

序列：
[({})]是合法的
{([})]不合法
{}合法
{[(])}不合法

用程序写逻辑检测这些字符串。

栈

当时没学栈的时候，一脸懵逼，其实上面的题用栈的就能很好解决。
什么是栈
栈（stack）又名堆栈，它是一种运算受限的线性表。
栈的特性：后进先出（Last In First Out）
栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
用ios oc语法数组实现一个简单的栈，来解决平衡符号问题。

算法可以描述如下：
做一个空栈，如果字符是一个开放字符，则将其推入栈中。如果字符是一个封闭符号与栈顶元素匹配，匹配上就出栈。如果栈为空则括号合法，否则不合法（还有没成队的括号t符）。

.h实现

#import <Foundation/Foundation.h>
NS_ASSUME_NONNULL_BEGIN


//用数组对栈的简单实现

@interface DataStack : NSObject

//入栈
-(void)push:(id)obj;

//出栈
-(void)pop;

//栈是否为空
-(BOOL)isEmpty;

//返回栈顶元素
-(id)topObj;

//从栈顶开始打印元素
-(void)printStackObj;

//清栈元素
-(void)clearStack;

@end

NS_ASSUME_NONNULL_END

.m实现

#import "DataStack.h"


//把数组的最后一个元素当作栈顶，来操作。
@interface DataStack ()
@property (nonatomic,strong) NSMutableArray * datas;

@end



@implementation DataStack

-(instancetype)init
{
    self = [super init];
    if (self) {
        self.datas = [NSMutableArray array];
       
    }
    return self;
}

//入栈
-(void)push:(id)obj
{
    [self.datas addObject:obj];
}

//出栈
-(void)pop
{
    if (self.datas.count == 0) {
        return;
    }
   
    [self.datas removeLastObject];
  
}

//栈是否为空
-(BOOL)isEmpty
{
    BOOL empty = (self.datas.count == 0)?YES:NO;
    return empty;
}

//返回栈顶元素
-(id)topObj
{
    return self.datas.lastObject;
}

//清栈
-(void)clearStack
{
    [self.datas removeAllObjects];
}

//从栈顶开始打印元素
-(void)printStackObj
{
    NSLog(@"从栈顶打印元素：");
    [self.datas enumerateObjectsWithOptions:NSEnumerationReverse usingBlock:^(id  _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
        NSLog(@"栈元素  ：%@",obj);
    }];
}

@end

在vc中测试

- (void)viewDidLoad {
    [super viewDidLoad];
    // Do any additional setup after loading the view.
    
    NSString * str1 = @"[({})]";
    NSString * str2 = @"{([})]";
    NSString * str3 = @"{[]()}";
     self.stack = [[DataStack alloc] init];
    
    [self inputString:str1];
    [self.stack clearStack];
    
    [self inputString:str2];
    [self.stack clearStack];
    
    [self inputString:str3];
    [self.stack clearStack];
}


-(void)inputString:(NSString *)str
{
    if (str.length == 0) {
        return ;
    }
    NSLog(@"输入的平衡符号：%@",str);
    NSString * singleStr = @"";
    NSString * combineStr = @"";
    
    //单个字符匹配
    for (NSInteger i = 0; i < str.length; i++) {
        NSRange   range =  NSMakeRange(i, 1);
        singleStr = [str substringWithRange:range];
        
        //如果是左边的符号就入栈,否则就和栈顶匹配
        if ([singleStr isEqualToString:@"{"]||[singleStr isEqualToString:@"["]||[singleStr isEqualToString:@"("]) {
            [self.stack push:singleStr];
        }else{
            //这里如果与栈顶d元素匹配就 出栈
            combineStr = [NSString stringWithFormat:@"%@%@",[self.stack topObj],singleStr];
            if ([combineStr isEqualToString:@"()" ]||[combineStr isEqualToString:@"[]" ]||[combineStr isEqualToString:@"{}" ]) {
                [self.stack pop]; //出栈
            }
        }
    }
    
    //看是否是空栈来判断 输入的平衡符是否正确
    if ([self.stack isEmpty])
    {
        NSLog(@"平衡符号的输入顺序完全正确！");
    }else{
        NSLog(@"平衡符号的输入顺序错误了！=====");
    }

}

最后

打印输出 ：

结果.png

总结：了解了栈---数据结构。