刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/basic-calculator-ii/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

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

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

思路

递归

最开始是想用递归来写的，但是发现递归实现比较复杂，而且实现出来之后数据太难看了，所以换用其他方式

栈

其实栈思路一开始就有，但是个人栈思路的题做的少，第一时间没有选择这个
关键就在于拆分元素和针对符号执行相应动作:

• 数字，可能多位，需要组合
• 空格，直接跳过
• +、- 需要将 数字/数字的负数 压入栈中，等待后续计算，因为有运算优先级存在，所以不能直接处理 +、- 算式，需要先保留
• *、/ 可以直接跟栈顶的数字进行计算
• 特殊情况1 第一个数字：因为第一个数字前不会出现符号，下一个符号出来时又其实代表的是下一个数字的行为，所以需要先预设一个+操作，然后让符号的动作滞后一个数字执行
• 特殊情况2 最后一个数字：最后一个数字解析出来后，并不会有下一个符号出现了，所以很可能出现无法进入处理的情况，所以需要增加一个最后一个字符等条件，保证处理上最后一个数字。

剩下的就简单了。老样子，细节在代码注释

代码

func calculate(s string) int {
	sBytes := []byte(s)
	// 暂存识别出的数字
	num := 0
	var stack []int
	// 预设一个符号，也就是第一个数字的处理模式
	sign := '+'
	
	for i, b := range sBytes {
		// 识别数字
		if b >= '0' && b <= '9' {
			num = num*10 + int(b-'0')
		}
		// 注意最后一个数字的处理 i == len(sBytes)-1
		if ((b > '9' || b < '0') && b != ' ') || i == len(sBytes)-1 {
			switch sign {
			// 加减不能直接算，这里符号其实是滞后的 
			// 所以现在的数字其实是符号后的数字，可能会出现后续数字需要优先计算乘除的情况
			case '+':
				stack = append(stack, num)
			case '-':
				stack = append(stack, -num)
			// 乘除直接算，题目保证算式有效，那就不会出问题
			case '*':
				stack[len(stack)-1] *= num
			case '/':
				stack[len(stack)-1] /= num
			}
			// 符号滞后执行
			sign = int32(b)
			// 计算后清空缓存的数字
			num = 0
		}
	}

	res := 0
	for _, i := range stack {
		res += i
	}
	return res
}