数据结构与算法

⭐️ 本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问。

学习数据结构与算法的关键在于掌握问题背后的算法思维框架，你的思考越抽象，它能覆盖的问题域就越广，理解难度也更复杂。在这个专栏里，小彭将基于 Java / Kotlin 语言，为你分享常见的数据结构与算法问题，及其解题框架思路。

本文是数据结构与算法系列的第 3 篇文章，完整文章目录请移步到文章末尾~

历史上的今天

2016 年 3 月 9 日，AlphaGo 大战李世石 拉开序幕。9 日至15 日，在韩国首尔举行的人机围棋比赛中，谷歌旗下 DeepMind 开发的人工智能围棋软件 AlphaGo 最终以 4:1 战胜世界围棋冠军、职业九段选手李世石。继 “深蓝” 战胜卡斯帕罗夫之后，这场比赛被视为人类与人工智能的又一场较量。—— 《了不起的程序员》

首先，你需要理解计算机是如何进行 “表达式求值” 的。我们平时使用的算术表达式，例如： 1 + 2 * 3，这种叫做 「中缀表达式」，也就是运算符都是放在两个操作数中间。中缀表达式符合人类的思考习惯，但是对计算机来说却并不友好，所以还有另外两种表达式形式：

中缀表达式： 二元运算符置于两个操作数之间，例如：(1 + 2) * 3
前缀表达式（波兰表达式）： 二元运算符置于两个操作数之间，例如：* + 1 2 3
后缀表达式（逆波兰表达式）： 二元运算符置于两个操作数之间，例如：1 2 + 3 *

相对于中缀表达式，前缀表达式和后缀表达式对计算机来说就友好很多了。它们在计算机看来却是比较简单易懂的结构，只需要依靠简单的入栈和出栈两种操作就可以完成计算。

我们以后缀表达式求值为例：

2.2 逆波兰表达式求值

后缀表达式也叫逆波兰表达式（Reverse Polish notation，RPN），逆波兰表达式求值步骤如下：

1、从左往右扫描逆波兰表达式：
2、如果是数字，直接入栈；
3、如果是运算符，那么弹出栈顶两个数字（四则运算需要两个运算数），执行运算；
4、将运算结果重新入栈；
5、重复步骤 3、4，直到遍历完成，最后栈中唯一的元素就是运算结果。

提示： 波兰表达式和逆波兰表达式是没有括号的，中缀表达式中的括号在转换过程中已经被 “消化”。

动画引用自 —— github.com/Mrxxd/LeetC…

参考代码：

kotlin复制代码class Solution {
    fun evalRPN(tokens: Array<String>): Int {
        if (tokens.isEmpty()) {
            return 0
        }

        val stack = ArrayDeque<Int>()

        for (token in tokens) {
            when (token) {
                "+" -> {
                    stack.push(stack.eval { o1, o2 -> o1 + o2 })
                }
                "-" -> {
                    stack.push(stack.eval { o1, o2 -> o1 - o2 })
                }
                "*" -> {
                    stack.push(stack.eval { o1, o2 -> o1 * o2 })
                }
                "/" -> {
                    stack.push(stack.eval { o1, o2 -> o1 / o2 })
                }
                else -> {
                    stack.push(token.toInt())
                }
            }
        }

        return stack.pop()
    }

    private fun Deque<Int>.eval(operator: (Int, Int) -> Int): Int {
        val num1 = pop()
        val num2 = pop()

        return operator(num2, num1)
    }
}

2.3 中缀 -> 逆波兰

逆波兰表达式求值很简单，但是我们的输入是普通的中缀表达式，我们要先转换为逆波兰表达式的形式，主要思想是 使用栈的特性来处理运算符和括号的优先级，步骤如下：

1、从左往右扫描中缀表达式；
2、如果是数字，直接输出；
3、如果是左括号（，直接入栈；
4、如果是右边括号），弹出栈顶元素，直到遇到左括号（；
5、如果是运算符，则需要判断跟栈顶运算符的优先级：
- 5.1 空栈或者优先级大于栈顶运算符，继续入栈；
- 5.2 优先级小于等于栈顶运算符，弹出栈顶运算符，并输出；
- 5.3 重复步骤 5.2，直到运算符大于栈顶运算符。
6、重复步骤 2、3、4、5，直到遍历完成，最后将栈中剩余元素出栈。

AC 代码

kotlin复制代码class Solution {
    fun calculate(s: String): Int {
        // 1、中缀表达式转换为逆波兰表达式
        // 2、逆波兰表达式求值
        return s.toRPN().evalRPN()
    }

    // ------------------------------------------------------------------------
    // 1、中缀表达式转换为逆波兰表达式
    // ------------------------------------------------------------------------

    private fun String.toRPN(): List<String> {

        val list = ArrayList<String>()
        val stack = ArrayDeque<Char>()

        var num = 0
        var sign = 1

        outerFor@
        for ((index, token) in this.withIndex()) {
            when (token) {
                ' ' -> continue@outerFor

                in '0'..'9' -> {
                    num = num * 10 + (token.toInt() - 48)
                    if (index + 1 >= length || !(this[index + 1] in '0'..'9')) {
                        list.add("${sign * num}")
                        num = 0
                    }
                }

                '(' -> stack.push(token)

                ')' -> {
                    while ('(' != stack.peek()) {
                        list.add("${stack.pop()}")
                    }
                    stack.pop() // 最后弹出 (
                }

                else -> {
                    // 先输出优先级相同或者更高的运算符
                    while (token.priority() <= stack.peek().priority()) {
                        list.add("${stack.pop()}")
                    }
                    stack.push(token)
                }
            }
        }
        while (stack.isNotEmpty()) {
            list.add("${stack.pop()}")
        }
        return list
    }

    // 运算符优先级
    private fun Char?.priority(): Int {
        return when (this) {
            '+', '-' -> 1
            '*', '/' -> 2
            null -> -1
            else -> -1
        }
    }

    // ------------------------------------------------------------------------
    // 2、逆波兰表达式求值
    // ------------------------------------------------------------------------

    private fun Deque<Int>.eval(operator: (Int, Int) -> Int): Int {
        if(size > 1){
            val num1 = pop()
            val num2 = pop()
            return operator(num2, num1)
        }else{
            // 类似 -1 + 1 的情况
            return operator(0, pop())
        }
    }

    private fun List<String>.evalRPN(): Int {

        val stack = ArrayDeque<Int>()

        for (token in this) {
            when (token) {
                "+" -> {
                    stack.push(stack.eval { o1, o2 -> o1 + o2 })
                }
                "-" -> {
                    stack.push(stack.eval { o1, o2 -> o1 - o2 })
                }
                "*" -> {
                    stack.push(stack.eval { o1, o2 -> o1 * o2 })
                }
                "/" -> {
                    stack.push(stack.eval { o1, o2 -> o1 / o2 })
                }
                else -> {
                    stack.push(token.toInt())
                }
            }
        }
        return stack.pop()
    }
}

推荐阅读
数据结构与算法系列完整目录如下（2023/07/11 更新）：

#1 链表问题总结

#2 链表相交 & 成环问题总结

#3 计算器与逆波兰表达式总结

#4 高楼丢鸡蛋问题总结

#5 为什么你学不会递归？谈谈我的经验

#6 回溯算法解题框架总结

#7 下次面试遇到二分查找，别再写错了

#8 什么是二叉树？

#9 什么是二叉堆 & Top K 问题

#10 使用前缀和数组解决 “区间和查询” 问题

#11 面试遇到线段树，已经这么卷了吗？

#12 使用单调队列解决 “滑动窗口最大值” 问题

#13 使用单调栈解决 “下一个更大元素” 问题

#14 使用并查集解决 “朋友圈” 问题

#15 如何实现一个优秀的 HashTable 散列表

#16 简答一波 HashMap 常见面试题

#17 二叉树高频题型汇总

#18 下跳棋，极富想象力的同向双指针模拟

Java & Android 集合框架系列文章: 跳转阅读

LeetCode 上分之旅系列文章：跳转阅读

⭐️ 永远相信美好的事情即将发生，欢迎加入小彭的 Android 交流社群~

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有

历史上的今天

目录

2.1 逆波兰表达式

2.2 逆波兰表达式求值

2.3 中缀 -> 逆波兰

推荐阅读