源码

首页 » 归档 » 源码 » 100天iOS数据结构与算法实战 Day05 – 栈的算法实战 Evaluate Reverse Polish Nota

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


前言

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]    

(0)

本文由 投稿者 创作,文章地址:https://blog.isoyu.com/archives/100tianiosshujujiegouyusuanfashizhan-day05-zhandesuanfashizhan-evaluate-reverse-polish-nota.html
采用知识共享署名4.0 国际许可协议进行许可。除注明转载/出处外,均为本站原创或翻译,转载前请务必署名。最后编辑时间为:4月 1, 2019 at 07:41 下午

热评文章

发表回复

[必填]

我是人?

提交后请等待三秒以免造成未提交成功和重复