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

前言

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

输入前：（3 + 2）*（4 + 6） 转化后：3 2 + 4 6 + * 结果：50

流程图

主要代码

- (int)evaluateRPN:(NSString *)inputStr
{
 DSStack *newStack = [[DSStack alloc] initWithSize:10];
 for (int i =0 ; i<inputStr.length; i++)
 {
 unichar tempChar = [inputStr characterAtIndex:i];
 if ([[NSString stringWithCharacters:&tempChar length:1] isEqualToString:@"*"])
 {
 NSNumber *a = [newStack popLastObject];
 NSNumber *b = [newStack popLastObject];
 [newStack push:[NSNumber numberWithInt:([a intValue]*[b intValue])]];
 }
 else if ([[NSString stringWithCharacters:&tempChar length:1] isEqualToString:@"/"])
 {
 NSNumber *a = [newStack popLastObject];
 NSNumber *b = [newStack popLastObject];
 [newStack push:[NSNumber numberWithInt:([a intValue]/[b intValue])]];
 }
 else if ([[NSString stringWithCharacters:&tempChar length:1] isEqualToString:@"+"])
 {
 NSNumber *a = [newStack popLastObject];
 NSNumber *b = [newStack popLastObject];
 [newStack push:[NSNumber numberWithInt:([a intValue]+[b intValue])]];
 }
 else if ([[NSString stringWithCharacters:&tempChar length:1] isEqualToString:@"-"])
 {
 NSNumber *a = [newStack popLastObject];
 NSNumber *b = [newStack popLastObject];
 [newStack push:[NSNumber numberWithInt:([a intValue]-[b intValue])]];
 }
 else
 {

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

 }
 return [[newStack popLastObject] intValue];

}

大致思路描述

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

• 100天iOS数据结构与算法实战 Day01

• 100天iOS数据结构与算法实战 Day02 - 栈

• 100天iOS数据结构与算法实战 Day03 - 栈的算法实战 Valid Parentheses

• 100天iOS数据结构与算法实战 Day04 - 栈的算法实战 逆波兰表示法

作者：人魔七七

链接：https://mp.weixin.qq.com/s/ZagroXeNb49YHtx8sD4yaA

本公众号转载内容已尽可能注明出处，如未能核实来源或转发内容图片有权利瑕疵的，请及时联系本公众号进行修改或删除【联系方式QQ : 3442093904  邮箱：support@cocoachina.com】。文章内容为作者独立观点，不代表本公众号立场。版权归原作者所有，如申请授权请联系作者，因文章侵权本公众号不承担任何法律及连带责任。

---END---