227. Basic Calculator II - cocoder39/coco39_LC GitHub Wiki
stackless
class Solution:
def calculate(self, s: str) -> int:
pre_op = '+'
pre_num = 0
cur_num = 0
res = 0
for i, ch in enumerate(s):
if ch.isdigit():
cur_num = 10 * cur_num + ord(ch) - ord('0')
if ch in '+-*/' or i == len(s) - 1:
if pre_op == '+': # pre_num + cur_num ch
res += pre_num
pre_num = cur_num
pre_op = ch
cur_num = 0
elif pre_op == '-': # pre_num - cur_num ch
res += pre_num
pre_num = -cur_num
pre_op = ch
cur_num = 0
elif pre_op == '*': # pre_num * cur_num ch
pre_num *= cur_num
pre_op = ch
cur_num = 0
elif pre_op == '/': # pre_num / cur_num ch
sign = 1 if pre_num >= 0 else -1
pre_num = abs(pre_num) // cur_num * sign
pre_op = ch
cur_num = 0
# 3 + 5 + 7 +
# 3 + 5*7 +
# 3 - 5*7
return res + pre_num
another stackless approach, use idea from lc 282, easier to understand
class Solution:
def calculate(self, s: str) -> int:
cur_num = 0
res = 0
pre_operand = 0
pre_op = '+'
for i, ch in enumerate(s):
if ch.isdigit():
cur_num = 10 * cur_num + ord(ch) - ord('0')
if ch in '+-*/' or i == len(s) - 1:
if pre_op == '+': # pre_operand + cur_num ch
res += cur_num
pre_operand = cur_num
elif pre_op == '-': # pre_operand - cur_num ch
res -= cur_num
pre_operand = -cur_num
elif pre_op == '*': # pre_operand * cur_num ch
res -= pre_operand
pre_operand *= cur_num
res += pre_operand
elif pre_op == '/': # pre_operand / cur_num ch
res -= pre_operand
sign = 1 if pre_operand >= 0 else -1
pre_operand = abs(pre_operand) // cur_num * sign
res += pre_operand
cur_num = 0
pre_op = ch
return res
stack approach
class Solution:
def calculate(self, s: str) -> int:
pre_op = '+'
cur_num = 0
stack = []
for i, ch in enumerate(s):
if ch.isdigit():
cur_num = 10 * cur_num + ord(ch) - ord('0')
if ch in '+-*/' or i == len(s) - 1:
if pre_op == '+': # pre_num + cur_num ch
stack.append(cur_num)
elif pre_op == '-': # pre_num - cur_num ch
stack.append(-cur_num)
elif pre_op == '*': # pre_num * cur_num ch
stack[-1] *= cur_num
elif pre_op == '/': # pre_num / cur_num ch
sign = 1 if stack[-1] >= 0 else -1
stack[-1] = abs(stack[-1]) // cur_num * sign
pre_op = ch
cur_num = 0
# 3 + 5 + 7 +
# 3 + 5*7 +
# 3 - 5*7
return sum(stack)
Notes 2024
thinking process:
- how to solve it if there is no * and /
- with * or /, we need to hold a few variables before applying them pre_num pre_op cur_num cur_op
- when we see cur_op, we need to use pre_op to decide how to process pre_num
- if pre_op == + or -, then res += pre_num
- if pre_op == * or /, then consolidated cur_num into pre_num
- rolling pre_num and pre_op with cur_num and cur_op accordingly. note that pre_num = -cur_num when pre_op == -
- when we see cur_op, we need to use pre_op to decide how to process pre_num
- by checking cur_op, we will have one last segment unprocessed. we can cover it by checking i == len(s) -1, this is like appending "+" to the end of the input string. now we have pre_num built, but not included in the final result
a few tricks:
- -3 // 2 = -2 instead of -1. the requirement is that division should truncate toward zero
-
if i == len(s) - 1 or ch in '+-*/':cannot be changed to elif. because we need to handle last digit which should go through both if branches
class Solution:
def calculate(self, s: str) -> int:
num = 0
stack = []
last_op = '+'
for ch in s:
if ch.isdigit():
num = num * 10 + ord(ch) - ord('0')
elif ch in '+-*/':
if last_op == '*':
stack[-1] *= num
elif last_op == '/':
val = stack[-1]
sign = 1 if val >= 0 else -1
stack[-1] = abs(val) // num * sign
elif last_op == '+':
stack.append(num)
elif last_op == '-':
stack.append(-num)
num = 0
last_op = ch
if last_op == '*':
stack[-1] *= num
elif last_op == '/':
val = stack[-1]
sign = 1 if val >= 0 else -1
stack[-1] = abs(val) // num * sign
elif last_op == '+':
stack.append(num)
elif last_op == '-':
stack.append(-num)
return sum(stack)
option 2: optimization without using stack (hard)
- keep track of last num, cur num, last op
- if last op is +/-, last num is always added to final res, last num gets value from cur num
- 1 +/- 2 +/-
- 1 +/- 2 *(or/)
- if last op is *(or/), res cannot be updated, last num = last num *(or/) cur num
- 1 (or/) 2 +/-/(or/)
class Solution:
def calculate(self, s: str) -> int:
cur_num = 0
last_num = 0
res = 0
last_op = '+'
for ch in s:
if ch.isdigit():
cur_num = cur_num * 10 + ord(ch) - ord('0')
elif ch in '+-*/':
if last_op == '*': # last_num * cur_num ch
last_num *= cur_num
elif last_op == '/': # last_num / cur_num ch
sign = 1 if last_num >= 0 else -1
last_num = abs(last_num) // cur_num * sign
elif last_op == '+': # last_num + cur_num ch
res += last_num
last_num = cur_num
elif last_op == '-': # last_num - cur_num ch
res += last_num
last_num = -cur_num
cur_num = 0
last_op = ch
if last_op == '*': # last_num * cur_num
last_num *= cur_num
res += last_num
elif last_op == '/': # last_num / cur_num
sign = 1 if last_num >= 0 else -1
last_num = abs(last_num) // cur_num * sign
res += last_num
elif last_op == '+': # last_num + cur_num
res += last_num + cur_num
elif last_op == '-': # last_num - cur_num
res += last_num - cur_num
return res
simplify code structure above. but attention to switch elif to if
class Solution:
def calculate(self, s: str) -> int:
cur_num = 0
last_num = 0
res = 0
last_op = '+'
for i, ch in enumerate(s):
if ch.isdigit():
cur_num = cur_num * 10 + ord(ch) - ord('0')
if ch in '+-*/' or i == len(s) - 1: # switch to if so after processing the last digit, it will execute the flow here
if last_op == '*': # last_num * cur_num ch
last_num *= cur_num
elif last_op == '/': # last_num / cur_num ch
sign = 1 if last_num >= 0 else -1
last_num = abs(last_num) // cur_num * sign
elif last_op == '+': # last_num + cur_num ch
res += last_num
last_num = cur_num
elif last_op == '-': # last_num - cur_num ch
res += last_num
last_num = -cur_num
cur_num = 0
last_op = ch
return res + last_num
============================================================================
int calculate(string s) {
stack<int> stk;
int i = 0;
char op = '+';
while (i < s.length()) {
//skip whitespaces
while (i < s.length() && s[i] == ' ') i++;
if (i >= s.length()) break;
if (isdigit(s[i])) {
// extract num
int num = 0;
while (i < s.length() && isdigit(s[i])) {
num = num * 10 + (s[i++] - '0');
}
if (op == '*') {
int tmp = stk.top();
stk.pop();
stk.push(tmp * num);
} else if (op == '/') {
int tmp = stk.top();
stk.pop();
stk.push(tmp / num);
} else if (op == '+') {
stk.push(num);
} else if (op == '-') {
stk.push(-num);
}
} else {
op = s[i++];
}
}
int res = 0;
while (! stk.empty()) {
res += stk.top();
stk.pop();
}
return res;
}