美文网首页iOS高手
数据结构与算法 - 逆波兰表达式求值

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

作者: 且行且珍惜_iOS | 来源:发表于2020-01-14 12:26 被阅读0次

    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

    相关文章

      网友评论

        本文标题:数据结构与算法 - 逆波兰表达式求值

        本文链接:https://www.haomeiwen.com/subject/oagoactx.html