100天iOS数据结构与算法实战 Day05 - 栈的算法实战 Evaluate Reverse Polish Nota

人魔七七 2019-04-01 10:54:08 755

前言

Day04介绍了Reverse Polish Notation,主要是为了方便用栈这个结构计算数学表达式。复习下:

输入前:(3 + 2)*(4 + 6) 转化后:3 2 + 4 6 + * 结果:50

流程图

QQ截图20190401105507.png

主要代码

  1. - (int)evaluateRPN:(NSString *)inputStr

  2. {

  3.    DSStack *newStack = [[DSStack alloc] initWithSize:10];

  4.    for (int i =0 ; i<inputStr.length; i++)

  5.    {

  6.        unichar tempChar = [inputStr characterAtIndex:i];

  7.        if ([[NSString stringWithCharacters:&tempChar length:1] isEqualToString:@"*"])

  8.        {

  9.            NSNumber *a = [newStack popLastObject];

  10.            NSNumber *b = [newStack popLastObject];

  11.            [newStack push:[NSNumber numberWithInt:([a intValue]*[b intValue])]];

  12.        }

  13.        else if ([[NSString stringWithCharacters:&tempChar length:1] isEqualToString:@"/"])

  14.        {

  15.            NSNumber *a = [newStack popLastObject];

  16.            NSNumber *b = [newStack popLastObject];

  17.            [newStack push:[NSNumber numberWithInt:([a intValue]/[b intValue])]];

  18.        }

  19.        else if ([[NSString stringWithCharacters:&tempChar length:1] isEqualToString:@"+"])

  20.        {

  21.            NSNumber *a = [newStack popLastObject];

  22.            NSNumber *b = [newStack popLastObject];

  23.            [newStack push:[NSNumber numberWithInt:([a intValue]+[b intValue])]];

  24.        }

  25.        else if ([[NSString stringWithCharacters:&tempChar length:1] isEqualToString:@"-"])

  26.        {

  27.            NSNumber *a = [newStack popLastObject];

  28.            NSNumber *b = [newStack popLastObject];

  29.            [newStack push:[NSNumber numberWithInt:([a intValue]-[b intValue])]];

  30.        }

  31.        else

  32.        {


  33.            [newStack push:[NSNumber numberWithInt:[[NSString stringWithCharacters:&tempChar length:1] intValue]]];

  34.        }


  35.    }

  36.    return [[newStack popLastObject] intValue];


  37. }

大致思路描述

  1. 把中缀表达式转化为Reverse Polish Notation。

  2. 按照顺序进栈。

  3. 当进栈的元素是 ( + - * / )四个运算符,则弹出栈顶两个元素并计算,并且把结果入栈。

  4. 最终栈只剩下一个元素,这个元素就是最后的值。

GitHubDemo

GitHub链接[1]    



References

[1] GithubDemo: https://github.com/renmoqiqi/100-Days-Of-iOS-DataStructure-Algorithm/tree/master/Day05