【LeetCode】227、基本计算器 II

【LeetCode】227、基本计算器 II

一、栈

1.1 栈

// go
func calculate(s string) int {
	// 需要解析字符串 里的每个 token
	// 本题不涉及括号, 只有+-*/, 所以涉及优先级: */的优先级比+-高
	// 为了处理优先级, 需要用栈: 即先遇到的+-都依次放入栈, 当遇到*/时优先一次性计算完, 再入栈
	// 最终栈内只有+-两种符号, 不存在优先级的问题, 则把栈内元素依次+-即可

	// 因为计算, 都是 "数" "符号" "数" 计算, 如 1 + 2, 3 / 5, 所以用两个栈: 数字栈和符号栈存储

	// 示例1:
	// 数字栈 [],  符号栈 []
	// 数字栈 [3], 符号栈 [+]
	// 数字栈 [3,2], 符号栈 [+,*]
	// 待入栈的2+, 遇到栈顶的2*里的乘号, 则需先pop(2*), 再计算(2*2=4), 再push(4+)
	// 数字栈 [3,4], 符号栈 [+,+]
	// 此时已遍历完, 站内只有+-了, 直接计算即可: 3+4+ = 7

	// 其中数字可能超过一位, 例如 123, 4563 等, 则需 cur 初值为 0, 并 cur = cur * 10 + (c - 'a') 来把字符串转为数字

	nums := []int{} // 数字栈
	ops := []byte{} // 符号栈
	cur := 0        // 遍历到的数字
	for _, c := range []byte(s + "+") { // 补全 "+" 是为了最后一对儿 num 和 op
		if c == ' ' { continue } // 不处理空格
		if c >= '0' && c <= '9' { // 遇到某位数字则 保留多位数字
			cur = cur*10 + int(c-'0') // 字符串转数字, 支持多位数字
		} else if l := len(nums); l == 0 || ops[l-1] == '+' || ops[l-1] == '-' { // 数字栈为空, 或, 栈顶为 +-, 则压栈
			nums = append(nums, cur); cur = 0  // 数字压栈, 压栈后, 清空当前数字
			ops = append(ops, c) // 符号压栈
		} else { // 遇到 */ 则 pop(), 并计算, 并 push()
			n := len(nums); topnum := nums[n-1]; nums = nums[:n-1] // nums.pop()
			o := len(ops); topop := ops[o-1]; ops = ops[:o-1] // ops.pop()

			tmp := 0 // 高优先级的 */ 的计算结果
			if topop == '*' {
				tmp = topnum * cur
			} else {
				tmp = topnum / cur
			}
            cur = 0

			nums = append(nums, tmp)
			ops = append(ops, c)
		}
	}
	return compute(nums, ops)
}

// 只有+-符号了
func compute(nums []int, ops []byte) int {
	n := len(nums)
    ans := nums[0]
	for i := 1; i < n; i++ {
		op := ops[i-1]
		if op == '+' {
			ans += nums[i]
		} else {
			ans -= nums[i]
		}
	}
	return ans
}

参考左神视频讲解

二、多语言解法

$Cpp/Go/Python/Rust/Js/Ts$

// cpp

// go 同上

# python

// rust

// js

// ts