LeetCode习题：计算器

题目描述：给定一个包含正整数、加(+)、减(-)、乘(*)、除(/)的算数表达式(括号除外)，计算其结果。表达式仅包含非负整数，+，- ，*，/ 四种运算符和空格 。 整数除法仅保留整数部分。

示例：

例1：
输入: "3+2*2"
输出: 7

例2：
输入: " 3/2 "
输出: 1

例3：
输入: " 3+5 / 2 "
输出: 5

解题思路：双栈计算。创建两个栈结构，分别用于保存数字和运算符，遍历字符串时，遇到运算符，将当前运算符与运算符栈的栈顶进行优先级比较，如果栈顶运算符优先级低于当前运算符，将数字和当前运算符直接入栈，如果栈顶运算符优先级高于或者等于当前运算符，取出数字栈和运算符栈栈顶数据，结合num保存的临时数据进行运算，运算结果依然保存到num，取出运算符栈新的栈顶数据，进行以上逻辑比较及运算或者直接入栈。最后依次取出两个栈中的数据进行运算，返回运算结果。

特别注意：由于一次计算后，紧接着从运算符栈出栈了一个数据，如果比较结果是无需继续计算，直接入栈，当该数据不为空时，记得将其重新入栈。

解题开发语言：Swift

struct ArrayStack {
    private var listData: [String]!
    private var n: Int!
    private var count: Int!

    // 栈顶元素
    public var stackTop: String? {
        if count == 0 {
            return nil
        }
        return listData[count-1]
    }

    init(num: Int) {
        listData = [String](repeating: "", count: num)
        n = num
        count = 0
    }

    // 入栈
    public mutating func push(item: String) -> Bool {
        if count == n {
            resize()
        }
        listData[count] = item
        count += 1
        return true
    }

    // 出栈
    public mutating func pop() -> String? {
        if count == 0 {
            return nil
        }
        let val = listData[count-1]
        count -= 1
        return val
    }

    // 是否为空
    public var isEmpty: Bool {
        return listData.isEmpty
    }

    // 清空栈
    public mutating func clear() {
        listData.removeAll()
        count = 0
    }

    // 扩充
    private mutating func resize() {
        var newAry = [String](repeating: "", count: n * 2)
        let range = newAry.startIndex..<newAry.index(newAry.startIndex, offsetBy: n)
        newAry.replaceSubrange(range, with: listData)
        listData = newAry
        n = n * 2
    }
}

class Solution {
    let numbers = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]
    let operators = ["+", "-", "*", "/"]
    func calculate(_ s: String) -> Int {
        // 数字栈
        var numberStack = ArrayStack(num:4)
        // 运算符栈
        var operatorStack = ArrayStack(num:2)
        // 保存多位数
        var num = ""
        for item in s {
            let char = String(item)
            if (numbers.contains(char)) {
                num += char
            } else if (operators.contains(char)) {
                var top = operatorStack.stackTop
                if (top == nil) {
                    numberStack.push(item: num)
                    num = ""
                    operatorStack.push(item: char)
                } else {
                    var judgeResult = judgeOperatorLevel(top!, char)
                    if (!judgeResult) {
                        numberStack.push(item: num)
                        num = ""
                        operatorStack.push(item: char)
                    } else {
                        top = operatorStack.pop()
                        while(judgeResult) {
                            let number = numberStack.pop()
                            num = getOperatorResult(num1: number!, num2: num, priority: top!)
                            top = operatorStack.pop()
                            if (top != nil) {
                                judgeResult = judgeOperatorLevel(top!, char)
                            } else {
                                judgeResult = false
                            }
                        }
                        numberStack.push(item: num)
                        num = ""
                        // 最后一次出栈的运算符不为空，重新入栈
                        if top != nil {
                            operatorStack.push(item: top!)
                        }
                        operatorStack.push(item: char)
                    }
                }
            }
        }
        var e = operatorStack.pop()
        while e != nil {
            let d = numberStack.pop()
            num = getOperatorResult(num1: d!, num2: num, priority: e!)
            e = operatorStack.pop()
        }
        return Int(num) ?? 0
    }
    
    // 判断运算符优先级(前者是否比后者优先级高)
    func judgeOperatorLevel(_ a: String, _ b: String) -> Bool {
        let aLevel = getOperatorLevel(a)
        let bLevel = getOperatorLevel(b)
        return aLevel >= bLevel
    }
    
    func getOperatorLevel(_ c: String) -> Int {
        if (c == "+" || c == "-") {
            return 1
        } else if (c == "*" || c == "/") {
            return 2
        } else {
            return 0
        }
    }
    
    // 运算
    func getOperatorResult(num1: String, num2: String, priority: String) -> String {
        let val1 = Int(num1) ?? 0
        let val2 = Int(num2) ?? 0
        var result: Int?
        switch priority {
        case "+":
            result = val1 + val2
            break
        case "-":
            result = val1 - val2
            break
        case "*":
            result = val1 * val2
            break
        case "/":
            result = val1 / val2
            break
        default:
            break
        }
        return String(result ?? 0)
    }
}

复杂度分析

时间复杂度：O(n), n为字符串长度，需要遍历整个字符串，代码中的while循环主要用于运算，所以执行次数与字符串中的运算符数量一致，如果是一个完整的没有空格的运算表达式，运算符数量 大概是 字符串长度的1/2，for + while 一起约等于 3n/2，忽略乘数因子，时间复杂度为O(n)

空间复杂度：O(1)，两个栈中最多保存两个运算符，4个数字，所以为O(1)

题目来源：LeetCode