[LeetCode] Medium - 227. Basic Calculator II (G,M,A,F)

Source From Here
Question
Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

Example 1:

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

Example 2:

Input: " 3/2 "
Output: 1

Example 3:

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

Note:

* You may assume that the given expression is always valid.
* Do not use the eval built-in library function.

Solution

Naive (Timeout)

view plaincopy to clipboardprint?

1. class Solution:  
2.     def calculate(self, s: str) -> int:  
3.         stack = []  
4.   
5.         # 0) Building stack  
6.         num = ''  
7.         for c in s.strip():  
8.             if c in ['+', '-', '*', '/']:  
9.                 stack.append(int(num))  
10.                 stack.append(c)  
11.                 num = ''  
12.                 continue  
13.             elif c == ' ':  
14.                 continue  
15.   
16.             num += c  
17.   
18.         if num:  
19.             stack.append(int(num))  
20.           
21.         def index_of(i):  
22.             for j in range(i, len(stack)):  
23.                 if stack[j] in ['*', '/']:  
24.                     return j  
25.   
26.             return -1  
27.   
28.         # 1) Start calculation  
29.         # 1.1) Handle high priority op (/,*)  
30.         i = index_of(0)  
31.         while i > 0:  
32.             hop = stack[i]  
33.             num1 = stack[i-1]  
34.             num2 = stack[i+1]              
35.             if hop == '/':  
36.                 stack[i-1:i+2] = [num1//num2]  
37.             else:  
38.                 stack[i-1:i+2] = [num1*num2]  
39.   
40.             i = index_of(i)  
41.           
42.         # 1.2) Handle low priority op (+/-)  
43.         while len(stack) > 1:  
44.             num1 = stack.pop(0)  
45.             op = stack.pop(0)  
46.             num2 = stack.pop(0)  
47.             if op == '+':  
48.                 stack.insert(0, num1 + num2)  
49.             else:  
50.                 stack.insert(0, num1 - num2)  
51.   
52.         # 2) Return the final result  
53.         return stack[0]  

Discussion - Python 3, Runtime 76ms, Stack Approach (link)

view plaincopy to clipboardprint?

1. class Solution:  
2.     def calculate(self, s: str) -> int:  
3.         num, preop, stack = '', '+', []  
4.   
5.         for c in s+'+':  
6.             if c.isdigit():  
7.                 num += c  
8.             elif c == ' ':  
9.                 continue  
10.             elif num != '':  
11.                 if preop == '+':  
12.                     stack.append(int(num))  
13.                 elif preop == '-':  
14.                     stack.append(int(num) * -1)  
15.                 elif preop == '*':  
16.                     stack.append(int(num) * stack.pop())  
17.                 else:  
18.                     stack.append(math.trunc(stack.pop()/int(num)))  
19.   
20.                 num = ''  
21.                 preop = c  
22.   
23.         return sum(stack)  

Runtime: 72 ms, faster than 92.89% of Python3 online submissions for Basic Calculator II.
Memory Usage: 14.6 MB, less than 88.89% of Python3 online submissions for Basic Calculator II.

Supplement
* Leetcode： 227 Basic Calculator II 讲解 (Cspiration 官方频道)