基本计算器

func calculate(s string) int {
    // 结尾补一个空格，保证所有数字都被计算到
    // 空格可以触发后面代码中 for 循环中将数字入栈的操作
    s += " "

    // 将中缀表达式转为后缀表达式，并保存到 tokens
    tokens := make([]string, 0, len(s))

    // 标识符，用作判断是否需要补 0，用作类似 -1 + 5 => 0 - 1 + 5 的场景
    needsZero := true
    // 保存遍历字符串遇到的符号
    // 因为存在括号，所以需要将部分符号临时保存到 opStack
    opStack := make([]string, 0, len(s))
    // 保存最近的数字，用字符串格式是为了便于整合完整数字并加入 tokens 数组
    num := ""
    // 遍历字符串
    for _, x := range s {
        // 如果是数字则暂作保留并立即进行下一轮便利（因为需要截取完整的数字）
        if '0' <= x && x <= '9' {
            num += string(x)
            needsZero = false
            continue
        } 
        // 如果缓存了数字
        if len(num) > 0 {
            // 将数字保存到 tokens 中，并将 num 变量初始化
            tokens = append(tokens, num)
            num = ""
        }

        // 如果遇到空格则略过，不能放在对缓存数字 num 的判断之前
        // 因为代码开头在字符串 s 的末尾加了空格，遍历到此空格时，会正好触发上面的将缓存数字 num 入栈的操作
        if x == ' ' {
            continue
        }

        // 左括号直接入栈
        if x == '(' {
            opStack = append(opStack, string(x))
            // 左括号后如果出现符号，则需要补零，如 1 + (-2 + 3)
            needsZero = true
            continue
        }
        // 右括号则将运算符号栈出栈，直至遇到左括号
        if x == ')' {
            for len(opStack) > 0 && opStack[len(opStack) - 1] != "(" {
                tokens = append(tokens, string(opStack[len(opStack) - 1]))
                opStack = opStack[:len(opStack) - 1]
            }
            // 将左括号出栈
            opStack = opStack[:len(opStack) - 1]
            //右括号后面出现符号只可能是运算符
            needsZero = false
            continue
        }
        
        // 如果需要补零
        // 该操作需要在判断运算符的操作之前
        if needsZero {
            tokens = append(tokens, "0")
            needsZero = false
        }

        // 判断当前运算符号优先级
        curRank := getRank(string(x))
        // 遍历符号栈，如果栈顶元素优先级大于当前元素，则将其加入 tokens
        // 比如, 2+3*5+4，遍历到 + 时，则需要将此前的 * 提取出来加入 tokens
        // 因为遇到 + 时，高优先级的内容已经计算完了
        // tokens:  [2, 3, 5]
        // opStack: [+, *]
        // ==> tokens: [2, 3, 5, *, +], opStack: []
        for len(opStack) > 0 && getRank(opStack[len(opStack) - 1]) >= curRank {
            tokens = append(tokens, string(opStack[len(opStack) - 1]))
            opStack = opStack[:len(opStack) - 1]
        }
        // 将当前运算符入栈
        opStack = append(opStack, string(x))
    }

    // 将符号栈内的剩余符号入栈
    for len(opStack)  > 0 {
        tokens = append(tokens, string(opStack[len(opStack) - 1]))
        opStack = opStack[:len(opStack) - 1]
    }   
    return evalRPN(tokens)
}

// getRank 判断运算符等级，乘除高于加减。
func getRank(op string) int {
    switch op {
        case "+", "-":
            return 1
        case "*", "/":
            return 2
    }
    return 0
} 


func evalRPN(tokens []string) int {
    // 定义栈
    stk := make([]int, 0, len(tokens))

    // 遍历数组
    for _, token := range tokens {
        // 判断是否是数字
        num, err := strconv.Atoi(token)
        // 将数字入栈
        if err == nil {
            stk = append(stk, num)
            continue
        }
        
        // 将最近两个数字取出并出栈
        num1, num2 := stk[len(stk) - 2], stk[len(stk) - 1]
        stk = stk[:len(stk) - 2]
        // 将最近两个数字通过运算符计算并将其入栈
        stk = append(stk, calc(num1, num2, token))
    }
    // 因为题目保证给定表达式必定有结果，所以直接返回栈中第一个元素
    return stk[0]
}

func calc(a, b int, op string) int {
    switch op {
        case "+":
            return a + b
        case "-":
            return a - b
        case "*":
            return a * b
        case "/":
            return a / b
    }
    return 0
}