算法 | 计算器系列 | 刷题打卡
点赞关注，不再迷路，你的支持对我意义重大！
Hi，我是丑丑。本文「数据结构 & 算法」| 导读 —— 登高博见 已收录，这里有 Android 进阶成长路线笔记 & 博客，欢迎跟着彭丑丑一起成长。（联系方式在 GitHub）
历史上的今天
2016 年 3 月 9 日，AlphaGo 大战李世石 拉开序幕。9 日至15 日，在韩国首尔举行的人机围棋比赛中，谷歌旗下 DeepMind 开发的人工智能围棋软件 AlphaGo 最终以 4:1 战胜世界围棋冠军、职业九段选手李世石。继 “深蓝” 战胜卡斯帕罗夫之后，这场比赛被视为人类与人工智能的又一场较量。—— 《了不起的程序员》
目录
1. 题目描述
- 224. Basic Calculator I
- 227. Basic Calculator II
- 772. Basic Calculator III 【题解】
- 770. Basic Calculator IV
- 150. Evaluate Reverse Polish Notation 【题解】
实现一个基本的计算器来计算一个简单的字符串表达式的值。
字符串表达式仅包含非负整数，+、 - 、*、/ 四种运算符，以及空格、左括号和右括号 。 整数除法仅保留整数部分。
这几道题其实是计算器系列题目：
- 第一道：加减法和括号
- 第二道：四则运算
- 第三道：四则运算 + 括号
理解了第三道的解法，相信前两道都不会有大问题。
2. 思路分析
2.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，直到遍历完成，最后栈中唯一的元素就是运算结果。
提示： 波兰表达式和逆波兰表达式是没有括号的，中缀表达式中的括号在转换过程中已经被 “消化”。
动画引用自 —— https://github.com/Mrxxd/LeetCodeAnimation
参考代码：
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，直到遍历完成，最后将栈中剩余元素出栈。
3. AC 代码
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()
}
}
创作不易，你的「三连」是丑丑最大的动力，我们下次见！
