数据结构与算法 - 逆波兰表达式求值

LeetCode 算法练习集合(Swift版)

目录

1. 逆波兰表达式求值
2. 合并两个有序链表 <==> 类似于合并两个有序数组
3. 合并 k 个排序链表，返回合并后的排序链表
4. 验证二叉搜索树
5. 二叉树的前中后层序遍历
6. 二叉树中的最大路径和
7. 二叉树展开为链表
8. 打家劫舍
9. 前 K 个高频元素

题目 1.逆波兰表达式求值

150: 根据逆波兰表示法，求表达式的值。
有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

• 整数除法只保留整数部分。
• 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

 示例 1：
 输入: ["2", "1", "+", "3", "*"]
 输出: 9
 解释: ((2 + 1) * 3) = 9

示例 2：
输入: ["4", "13", "5", "/", "+"]
输出: 6
解释: (4 + (13 / 5)) = 6

 示例 3：
 输入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
 输出: 22
 解释:
 ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
 = ((10 * (6 / (12 * -11))) + 17) + 5
 = ((10 * (6 / -132)) + 17) + 5
 = ((10 * 0) + 17) + 5
 = (0 + 17) + 5
 = 17 + 5
 = 22

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/evaluate-reverse-polish-notation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

思路示意图

代码

import Foundation

//判断是否是操作符
func isOperator(string: String) -> Bool {
    return ("+-*/" as NSString).contains(string)
}
// 计算每一项的结果： 左操作数 操作符 右操作数 = 值
func calculate(left: Int, right: Int, operatorStr: String) -> Int {
    switch operatorStr {
    case "+":
        return left + right
    case "-":
        return left - right
    case "*":
        return left * right
    case "/":
        return left / right
    default:
        return 0
    }
}

//返回逆波兰表达式的值  时间复杂度O(n) 
func evalRPN(tokens: [String] ) -> Int? {
    //数组 模拟 栈
    var stack: [Int] = [];
    
    for string in tokens {
        //操作符
        if isOperator(string: string) {
            // 右操作数
            let right = stack.last
            //出栈
            stack.removeLast();
            // 左操作数
            let left = stack.last;
            //出栈
            stack.removeLast();
            //把计算结果入栈
            let value = calculate(left: left!, right: right!, operatorStr: string);
            stack.append(value);
        }else {
            //入栈
            stack.append(Int(string)!)
        }
    }
    return stack.first
}

// 输入的逆波兰表达式
let input = ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
let value = evalRPN(tokens: input)
print("逆波兰表达式 \(input) \n值：\(value ?? 0)")

推荐学习资料:

Swift从入门到精通
恋上数据结构与算法（一）
恋上数据结构与算法（二）
每周一道算法题

如果需要跟我交流的话：
※ Github： https://github.com/wsl2ls
※ 简书：https://www.jianshu.com/u/e15d1f644bea
※ 微信公众号：iOS2679114653
※ QQ群：835303405