227. Basic Calculator II

Problem

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.

Problem Summary

Given a string expression s, implement a basic calculator to evaluate it and return its value. Integer division should keep only the integer part.

Solution Approach

• This problem is an enhanced version of Problem 224. Problem 224 only has addition, subtraction, and parentheses, while this problem adds multiplication and division. Since multiplication and division have higher precedence than addition and subtraction, first calculate the multiplication and division operations, then replace the calculated results back into the original expression. Finally, only addition and subtraction remain, so the problem is reduced to Problem 224.
• Push the numbers after addition and subtraction operators onto the stack. When encountering multiplication or division, directly calculate it with the top element of the stack, and put the calculated result back on the top of the stack. If an operator is read, or the traversal reaches the end of the string, it is considered that the end of a number has been reached. After processing this number, update preSign to the current traversed character. After traversing string s, sum the elements in the stack, which is the value of this string expression. Time complexity is O(n), and space complexity is O(n).

Code

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
}