KK's blog

每天积累多一些

0%

LeetCode 227 Basic Calculator II

Posted on Edited on Disqus:

LeetCode



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

The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-2<sup>31</sup>, 2<sup>31</sup> - 1].

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:

Input: s = “3+22”
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<sup>5</sup>
s consists of integers and operators `(‘+’, ‘-‘, ‘‘, ‘/‘)separated by some number of spaces. *srepresents **a valid expression**. * All the integers in the expression are non-negative integers in the range[0, 231 - 1]`.
The answer is guaranteed to fit in a *32-bit integer.

题目大意：

实现字符串加减乘除，但无括号。

算法思路：

逆波兰式的实现用Stack。Stack只存数，而且只存加号操作符的数，也就是说，
如果是减，就将-num入栈，
如果是乘除，立刻计算stack[-1]乘除num的结果再压入栈，因为乘除是最高优先级可以直接计算，而加减不可以。
所以用一个stack

代码中含三种情况：空格，运算符，数字

LeetCode 224 Basic Calculator 括号加减法, 同一层括号内求和遇括号入栈
LeetCode 227 Basic Calculator II 加减乘除, 和的每一项入栈，方便出栈计乘除
LeetCode 772 Basic Calculator III 加减乘除括号, L227的递归版

注意事项：

此题没有括号，不能用模板，要借用op来记录前一个操作符

  1. op记录前一个运算符，char为运算符或当前字符。计算时候根据op，因为char(+)只是第二个操作数(1-2+)的终结字符，此时表明操作数stack[-1], num以及操作符op均已完成，可以计算
  2. 最容易错的是向下取整Line 18, 题目返回要求整数。所以要除法后取整int(prev / num)
  3. s末尾加入加号，方便parse最后一个num

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def calculate(self, s: str) -> int:
	s += '+'
	res, num, stack, op = 0, 0, [], '+'
	for char in s:
		if char == ' ':
			continue
		elif char.isdigit():
			num = num * 10 + int(char)
		elif op == '-':
			stack.append(-num)
		elif op == '+':
			stack.append(num) # [4+2*1]
		elif op == '*':
			prev = stack.pop()
			stack.append(prev * num)
		elif op == '/':
			prev = stack.pop()
			stack.append(int(prev / num))  # remember
		if char in '+-*/':
			num = 0
			op = char
    return sum(stack)

算法分析：

时间复杂度为O(n)，空间复杂度O(n)

Free mock interview