LeetCode - #227 基于 Swift 实现基本计算器

摘要

在这篇文章中，我们将实现一个基于 Swift 语言的基本计算器。该计算器能够解析和计算包含 +、-、* 和 / 的数学表达式，并且遵循运算符的优先级规则。整数除法仅保留整数部分，不能使用 eval() 这样的内置解析方法。

描述

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

整数除法仅保留整数部分。

你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。

注意： 不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：

输入： s = "3+2*2"
输出： 7

示例 2：

输入： s = " 3/2 "
输出： 1

示例 3：

输入： s = " 3+5 / 2 "
输出： 5

提示：

• 1 <= s.length <= 3 * 105
• s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开
• s 表示一个 有效表达式
• 表达式中的所有整数都是非负整数，且在范围 [0, 231 - 1] 内
• 题目数据保证答案是一个 32-bit 整数

题解答案

我们可以使用 栈（Stack） 来处理乘法和除法运算的优先级，同时遍历字符串，进行逐步计算。主要步骤如下：

1. 遍历字符串 s，跳过空格。
2. 当遇到数字时，将其解析出来。
3. 当遇到运算符 +、-、*、/ 时，根据之前的运算符决定如何处理：
   • + 直接将数字加入栈。
   • - 取相反数并加入栈。
   • * 取出栈顶元素，与当前数字相乘后再压入栈。
   • / 取出栈顶元素，与当前数字做整数除法后再压入栈。
4. 遍历结束后，栈中的所有元素求和即为最终结果。

题解代码

import Foundation

func calculate(_ s: String) -> Int {
    var stack: [Int] = []
    var num = 0
    var sign: Character = "+"
    let chars = Array(s)
    
    for (i, char) in chars.enumerated() {
        if char.isNumber {
            num = num * 10 + char.wholeNumberValue!
        }
        
        if "+-*/".contains(char) || i == chars.count - 1 {
            switch sign {
                case "+": stack.append(num)
                case "-": stack.append(-num)
                case "*": stack.append(stack.removeLast() * num)
                case "/": stack.append(stack.removeLast() / num)
                default: break
            }
            sign = char
            num = 0
        }
    }
    
    return stack.reduce(0, +)
}

// 示例测试
let expr1 = "3+2*2"
let expr2 = " 3/2 "
let expr3 = " 3+5 / 2 "

print(calculate(expr1))  // 输出: 7
print(calculate(expr2))  // 输出: 1
print(calculate(expr3))  // 输出: 5

题解代码分析

1. 解析数字：num = num * 10 + char.wholeNumberValue! 逐步解析多位数字。
2. 处理运算符：当遇到 +、-、*、/ 时，
   • + 和 - 直接将数值（或其相反数）压入栈。
   • * 和 / 取出栈顶元素，与当前数值计算后再压入栈。
3. 求和：最后对栈中所有元素求和得到最终结果。

示例测试及结果

calculate("3+2*2") // 输出: 7
calculate(" 3/2 ") // 输出: 1
calculate(" 3+5 / 2 ") // 输出: 5

时间复杂度

• 遍历字符串一次： O(n)
• 入栈出栈操作： O(1)（均摊）
• 最终求和： O(n)

综合来看，时间复杂度为 O(n)。

空间复杂度

• 额外使用 stack 来存储运算结果，最坏情况下存储 n/2 个数，空间复杂度为 O(n)。

总结

• 通过 栈 来处理 * 和 / 的优先级问题。
• 逐步解析数字，遇到操作符时再处理。
• 遍历结束后计算栈内所有元素的总和 即可得到最终结果。
• 时间复杂度 O(n)，空间复杂度 O(n)，适用于大规模输入。