227. Basic Calculator II

题目

Given a string s which represents an expression, evaluate this expression and return its value.

The integer division should truncate toward zero.

Example 1:

Input: s = "3+2*2"
Output: 7

Example 2:

Input: s = " 3/2 "
Output: 1

Example 3:

Input: s = " 3+5 / 2 "
Output: 5

Constraints:

• 1 <= s.length <= 3 * 10^5
• s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.
• s represents a valid expression.
• All the integers in the expression are non-negative integers in the range [0, 2^31 - 1].
• The answer is guaranteed to fit in a 32-bit integer.

题目大意

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。整数除法仅保留整数部分。

解题思路

• 这道题是第 224 题的加强版。第 224 题中只有加减运算和括号，这一题增加了乘除运算。由于乘除运算的优先级高于加减。所以先计算乘除运算，将算出来的结果再替换回原来的算式中。最后只剩下加减运算，于是题目降级成了第 224 题。
• 把加减运算符号后面的数字压入栈中，遇到乘除运算，直接将它与栈顶的元素计算，并将计算后的结果放入栈顶。若读到一个运算符，或者遍历到字符串末尾，即认为是遍历到了数字末尾。处理完该数字后，更新 preSign 为当前遍历的字符。遍历完字符串 s 后，将栈中元素累加，即为该字符串表达式的值。时间复杂度 O(n)，空间复杂度 O(n)。

代码

package leetcode

func calculate(s string) int {
	stack, preSign, num, res := []int{}, '+', 0, 0
	for i, ch := range s {
		isDigit := '0' <= ch && ch <= '9'
		if isDigit {
			num = num*10 + int(ch-'0')
		}
		if !isDigit && ch != ' ' || i == len(s)-1 {
			switch preSign {
			case '+':
				stack = append(stack, num)
			case '-':
				stack = append(stack, -num)
			case '*':
				stack[len(stack)-1] *= num
			default:
				stack[len(stack)-1] /= num
			}
			preSign = ch
			num = 0
		}
	}
	for _, v := range stack {
		res += v
	}
	return res
}