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

人魔七七 2019-03-29 09:51:22 542

题目描述:

输入前:(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.        else if ([[NSString stringWithCharacters:&tempChar length:1] isEqualToString:@"("])

  18.        {

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

  20.        }

  21.        //6

  22.        else if ([[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]