网站设计公司发展_山西网站建设推荐咨询_网站综合排名信息查询_百度新闻网

【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 和 opif 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 = 0nums = 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