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

题目描述：

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

我们主要用他来做什么

在1960和1970年代， 逆波兰记法 [1]   广泛地被用于台式计算器，因此也在普通公众（工程、商业和金融领域）中使用。

后面我们一个类似计算器的算法题和这个有关，所以我们先看看这个吧。

上述例子的示意图

步骤一

步骤二

步骤三

步骤四

步骤五

步骤六

步骤七

步骤八

步骤九

步骤十

步骤十一

主要代码

1. -(NSString*)infixToPostfix:(NSString*)inputStr

2. {

3. //1

4.    NSMutableString*resultsStr =[@"" mutableCopy];

5.    //2

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

7.    //3

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

9.    {

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

11.        //4

12.        if([self inputShouldNumber:[NSString stringWithCharacters:&tempChar length:1]])

13.        {

14.            [resultsStr appendString:[NSString stringWithCharacters:&tempChar length:1]];

15.        }

16.        //5

17.        elseif([[NSString stringWithCharacters:&tempChar length:1] isEqualToString:@"("])

18.        {

19.            [newStack push:[NSString stringWithCharacters:&tempChar length:1]];

20.        }

21.        //6

22.        elseif([[NSString stringWithCharacters:&tempChar length:1] isEqualToString:@")"])

23.        {

24.            while([newStack sizeOfStack]>0&&![[newStack peek] isEqualToString:@"("])

25.            {

26.                [resultsStr appendString:[newStack popLastObject]];

27.            }

28.            if([newStack sizeOfStack]>0&&![[newStack peek] isEqualToString:@"("])

29.            {

30.                return@"无效的表达式";

31.            }

32.            else

33.            {

34.                [newStack popLastObject];

35.            }

36.        }

37.        //7

38.        else

39.        {

40.            while([newStack sizeOfStack]>0&&[self operatorOfPriority:[NSString stringWithCharacters:&tempChar length:1]]<=[self operatorOfPriority:[newStack peek]])

41.            {

42.                [resultsStr appendString:[newStack popLastObject]];

43.            }

44.            [newStack push:[NSString stringWithCharacters:&tempChar length:1]];

45.        }

46.    }

47.    //8

48.    while([newStack sizeOfStack]>0)

49.    {

50.        [resultsStr appendString:[newStack popLastObject]];

51.    }

52.    return resultsStr;

53. }

代码思路描述

1. 初始化一个空字符串

2. 初始化一个空栈

3. 读取遍历每个字符

4. 如果读取的字符是数字，则拼接

5. 如果读取的字符是‘（’，则进栈

6. 如果读取的字符是‘）’，先把‘（’ 之前的出栈并拼接，然后这个‘（’ 再 出栈

7. 如果读取的是 + ,-, ,/。如果栈非空并且这个（ + ,-, ,/ ）优先级小于等于栈顶的元素的优先级,遍历出栈并拼接，否则进栈

8. 把剩下的元素一一出栈并拼接

代码链接

GithubDemo [2]

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

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

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