LeetCode.224.基本计算器（困难）

题目

LeetCode.224.基本计算器（困难）

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

提示：

• 1 <= s.length <= 3 * 105
• s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
• s 表示一个有效的表达式

题解

思路

• 表达式计算是从左到右遍历的，所以从左到右遍历字符串。
• 用result变量记录左边已经计算过的表达式的值。
• 新的表达式计算出来后，与result累加结果。

操作数识别

• 遇到连续数字，就做累加。
• 每遇到一个数字字符，把前面累加的结果乘以十，再加上当前数字值。

什么时候停止累加操作数？

遇到非数字字符操作数就可以确定了。

遇到的非数字字符可能会有：+、-、(、)。

运算符

• 只有加减运算，优先级相同。
• 可以把减法当作加法，识别完操作数，如果前面是减号，就当作负数。
• 用一个sign变量记录运算符，为1表示操作数前是加号，为-1表示操作数前是减号。
• 操作数识别完后，乘以sign，再与result累加。

括号

• 多括号时，优先计算最内层的括号。
• 遇到左括号时，左侧表达式需要等待括号内表达式计算得出结果才能继续计算，所以需要暂存左侧表达式之前累加的结果和运算符。
• 括号会有嵌套，需要保存每一层括号的临时计算结果，且是从左向右遍历的，访问临时计算结果又是从右到左，所以用栈存储。
• 遇到右括号时，需要从栈中取出之前临时状态继续运算。

题解1：暴力递归

class Solution {
    // 记录
    data class ExpResult(val value: Int, val endIndex: Int)

    fun calculate(s: String): Int {
        val n = s.length

        fun cal(i: Int): ExpResult {
            var result = 0
            var operand = 0
            var sign = 1
            var j = i
            while (j < n) {
                val c = s[j]
                if (c in '0'..'9') {
                    // 识别操作数
                    operand = operand * 10 + (c - '0')
                } else {
                    // 确定操作数，累加到结果中
                    result += sign * operand
                    operand = 0
                    when (c) {
                        '+' -> sign = 1
                        '-' -> sign = -1
                        '(' -> {
                            val exp = cal(j + 1)
                            result += sign * exp.value
                            j = exp.endIndex
                        }
                        ')' -> return ExpResult(result, j)
                    }
                }
                j++
            }
            // 末尾没有运算符，手动触发累加
            result += sign * operand
            return ExpResult(result, n - 1)
        }

        return cal(0).value
    }
}

题解2：基于迭代的栈

import java.util.*

class Solution {
    /**
     * 由于只包含加法和减法，减法可以看作是加负数，统一为加法，只需要处理好括号确定的操作符最终是什么就可以直接相加了
     */
    fun calculate(s: String): Int {
        // 操作数
        var operand = 0
        // 符号，1表示减法，-1表示减法
        var sign = 1
        // 开括号前的运算结果
        var result = 0
        // 存储括号前的结果和开括号前的运算符
        val stack = Stack<Int>()
        for (char in s) {
            when (char) {
                in '0'..'9' -> {
                    operand = operand * 10 + (char - '0')
                }
                '+' -> {
                    // 遇到加号，先计算出加号前面的结果
                    result += sign * operand
                    // 记录当前操作符是加号
                    sign = 1
                    // 操作数重置
                    operand = 0
                }
                '-' -> {
                    // 遇到减号，先计算出加号前面的结果
                    result += sign * operand
                    // 记录当前操作符是加号
                    sign = -1
                    // 操作数重置
                    operand = 0
                }
                '(' -> {
                    // 遇到开括号，先计算出括号前面的结果
                    result += sign * operand
                    // 将开括号前的运算结果和运算符入栈
                    stack.push(result)
                    stack.push(sign)
                    // 重置临时结果和操作符，以便于运算括号内的结果
                    sign = 1
                    result = 0
                    // 可以重置操作数，不过开括号前一定是一个操作符，操作符中已经重置过了
                }
                ')' -> {
                    // 遇到闭括号，先计算出括号的结果
                    result += sign * operand
                    // result此时为括号内的结果，需要乘以括号前的符号，再和括号前的结果合并
                    result *= stack.pop()
                    result += stack.pop()
                    // 重置操作数
                    // 闭括号后可能继续跟着操作符，也可能没有跟操作符
                    // 如果跟着操作符，可以不在此重置，因为遇到操作符会重置
                    // 如果没跟着操作符，说明整个表达式结束了，为了不影响最后的通式运算，这里重置运算数
                    operand = 0
                }
            }
        }
        // 最后可能没有括号了，而上面是遇到了操作符才去计算操作符前面的结果
        // 现在在已经达到尾部了，没有操作符了，最后结算一次
        return result + sign * operand
    }
}