每日算法 基本计算器

例题：224. 基本计算器

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

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

示例 1：

输入：s = "1 + 1"
输出：2

示例 2：

输入：s = " 2-1 + 2 "
输出：3

示例 3：

输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23

package main

import (
    "fmt"
)

// 计算
func calc1(nums *[]int, ops *[]byte) {
    b := (*nums)[len(*nums)-1]
    a := (*nums)[len(*nums)-2]
    *nums = (*nums)[:len(*nums)-2] // 弹出两个操作数(代表已处理)

    op := (*ops)[len(*ops)-1]
    *ops = (*ops)[:len(*ops)-1] // 弹出两个操作数的运算符(代表已处理)

    switch op {
    case '+':
        *nums = append(*nums, a+b)
    case '-':
        *nums = append(*nums, a-b)
    case '*':
        *nums = append(*nums, a*b)
    case '/':
        *nums = append(*nums, a/b)
    }
}

// 优先级
func pri(op byte) int {
    if op == '+' || op == '-' {
        return 1
    }
    if op == '*' || op == '/' {
        return 2
    }
    return 0
}

func calculate(s string) int {
    nums := make([]int, 0) // 数字栈
    ops := make([]byte, 0) // 运算符栈

    prev := byte(0) // 记录上一个非空格字符，用于处理负数
    for i := 0; i < len(s); i++ {
        c := s[i]

        // 空格跳过
        if c == ' ' {
            continue
        }

        // 数字：连续读取完整整数
        if c >= '0' && c <= '9' {
            num := 0
            digitCount := i
            for digitCount < len(s) && s[digitCount] >= '0' && s[digitCount] <= '9' {
                num = num*10 + int(s[digitCount]-'0')
                digitCount++
            }
            nums = append(nums, num)
            prev = 'n'
            continue
        }

        // 左括号直接压栈
        if c == '(' {
            ops = append(ops, c)
            prev = c
            continue
        }

        // 右括号：算到左括号为止
        if c == ')' {
            for len(ops) > 0 && ops[len(ops)-1] != '(' {
                calc1(&nums, &ops)
            }
            if len(ops) > 0 {
                ops = ops[:len(ops)-1] // 弹出 '('
            }
            prev = c
            continue
        }

        // 处理负数：如果 '-' 前面是开头或 '('，补一个 0，变成 0-x，这样就不影响处理了
        if c == '-' && (prev == 0 || prev == '(') {
            nums = append(nums, 0)
        }

        // 判断当前计算符与栈顶计算符优先级，防止加减优先于乘除
        for len(ops) > 0 && ops[len(ops)-1] != '(' && pri(ops[len(ops)-1]) >= pri(c) {
            calc1(&nums, &ops)
        }
        ops = append(ops, c)
        prev = c
    }

    // 把剩余运算符算完
    for len(ops) > 0 {
        calc1(&nums, &ops)
    }

    return nums[0]
}

func main() {
    fmt.Println(calculate("1 + 1"))               // 2
    fmt.Println(calculate(" 2-1 + 2 "))           // 3
    fmt.Println(calculate("(1+(4+5+2)-3)+(6+8)")) // 23
    fmt.Println(calculate("3+5*2-(8/4+1)"))       // 10
    fmt.Println(calculate("-1 + 2"))              // 1
    fmt.Println(calculate("-1 + (-2+3)"))         // 0
}

这道题难度在于 ( ) 导致的二维问题，需要双栈处理，剩下的就是边界处理了。（其实边界处理也不亚于双栈引入处理，两个中等难的东西叠在一起就变成困难了）