題目描述：給定一個(gè)包含正整數(shù)陨界、加(+)榕酒、減(-)、乘(*)质帅、除(/)的算數(shù)表達(dá)式(括號除外)烈疚，計(jì)算其結(jié)果黔牵。表達(dá)式僅包含非負(fù)整數(shù)，+爷肝，- 猾浦，*，/ 四種運(yùn)算符和空格 灯抛。 整數(shù)除法僅保留整數(shù)部分金赦。

示例：

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

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

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

解題思路：雙棧計(jì)算。創(chuàng)建兩個(gè)棧結(jié)構(gòu)对嚼，分別用于保存數(shù)字和運(yùn)算符夹抗，遍歷字符串時(shí)，遇到運(yùn)算符纵竖，將當(dāng)前運(yùn)算符與運(yùn)算符棧的棧頂進(jìn)行優(yōu)先級比較漠烧，如果棧頂運(yùn)算符優(yōu)先級低于當(dāng)前運(yùn)算符，將數(shù)字和當(dāng)前運(yùn)算符直接入棧磨确，如果棧頂運(yùn)算符優(yōu)先級高于或者等于當(dāng)前運(yùn)算符沽甥，取出數(shù)字棧和運(yùn)算符棧棧頂數(shù)據(jù)，結(jié)合num保存的臨時(shí)數(shù)據(jù)進(jìn)行運(yùn)算乏奥，運(yùn)算結(jié)果依然保存到num摆舟，取出運(yùn)算符棧新的棧頂數(shù)據(jù)，進(jìn)行以上邏輯比較及運(yùn)算或者直接入棧。最后依次取出兩個(gè)棧中的數(shù)據(jù)進(jìn)行運(yùn)算恨诱，返回運(yùn)算結(jié)果媳瞪。

特別注意：由于一次計(jì)算后，緊接著從運(yùn)算符棧出棧了一個(gè)數(shù)據(jù)照宝，如果比較結(jié)果是無需繼續(xù)計(jì)算蛇受，直接入棧，當(dāng)該數(shù)據(jù)不為空時(shí)厕鹃，記得將其重新入棧兢仰。

解題開發(fā)語言：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
    }

    // 擴(kuò)充
    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 {
        // 數(shù)字棧
        var numberStack = ArrayStack(num:4)
        // 運(yùn)算符棧
        var operatorStack = ArrayStack(num:2)
        // 保存多位數(shù)
        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 = ""
                        // 最后一次出棧的運(yùn)算符不為空，重新入棧
                        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
    }
    
    // 判斷運(yùn)算符優(yōu)先級(前者是否比后者優(yōu)先級高)
    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
        }
    }
    
    // 運(yùn)算
    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)
    }
}

復(fù)雜度分析

時(shí)間復(fù)雜度：O(n), n為字符串長度剂碴，需要遍歷整個(gè)字符串把将，代碼中的while循環(huán)主要用于運(yùn)算，所以執(zhí)行次數(shù)與字符串中的運(yùn)算符數(shù)量一致忆矛，如果是一個(gè)完整的沒有空格的運(yùn)算表達(dá)式察蹲，運(yùn)算符數(shù)量 大概是 字符串長度的1/2，for + while 一起約等于 3n/2催训，忽略乘數(shù)因子洽议，時(shí)間復(fù)雜度為O(n)

空間復(fù)雜度：O(1)，兩個(gè)棧中最多保存兩個(gè)運(yùn)算符漫拭，4個(gè)數(shù)字亚兄，所以為O(1)

題目來源：LeetCode