目录
1. 题目描述
实现一个基本的计算器来计算一个简单的字符串表达式的值。
字符串表达式仅包含非负整数,+、 - 、*、/ 四种运算符,以及空格、左括号和右括号 。 整数除法仅保留整数部分。
这几道题其实是计算器系列题目:
- 第一道:加减法和括号
- 第二道:四则运算
- 第三道:四则运算 + 括号
理解了第三道的解法,相信前两道都不会有大问题。
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,直到遍历完成,最后栈中唯一的元素就是运算结果。
提示: 波兰表达式和逆波兰表达式是没有括号的,中缀表达式中的括号在转换过程中已经被 “消化”。
动画引用自 —— github.com/Mrxxd/LeetC…
参考代码:
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() } }