Đề bài: Tính giá trị biểu thức string chỉ chứa số nguyên không âm, +, -, *, /, space. Phép chia lấy phần nguyên (truncate toward zero). Không có dấu ngoặc.
Ví dụ: "3+2*2" → 7.
Ý tưởng: Stack Xử Lý Độ Ưu Tiên * / Trước + -
Duyệt string, parse số. Khi gặp operator:
+: push số hiện tại.-: push -số hiện tại.*: pop stack top, nhân với số hiện tại, push kết quả./: pop stack top, chia cho số hiện tại (truncate toward 0), push kết quả.
Cuối cùng sum stack = kết quả.
Code Python
class Solution:
def calculate(self, s: str) -> int:
# Remove spaces
s = s.replace(' ', '')
n = len(s)
stack = []
num = 0
sign = '+' # Previous operator (treat first number as +num)
for i, ch in enumerate(s):
if ch.isdigit():
num = num * 10 + int(ch)
# If operator or last character
if not ch.isdigit() or i == n - 1:
if sign == '+':
stack.append(num)
elif sign == '-':
stack.append(-num)
elif sign == '*':
stack.append(stack.pop() * num)
elif sign == '/':
# Python // truncates toward -inf, need toward 0
prev = stack.pop()
if prev < 0:
stack.append(-(-prev // num))
else:
stack.append(prev // num)
sign = ch
num = 0
return sum(stack)
# Test
ob = Solution()
print(ob.calculate("3+2*2")) # 7
print(ob.calculate(" 3/2 ")) # 1
print(ob.calculate(" 3+5 / 2 ")) # 5
print(ob.calculate("14-3/2")) # 13
print(ob.calculate("-3+5")) # 2 (note: leading - handled as 0-3+5)
Xử lý chia truncate toward zero
Python // truncate toward -inf (ví dụ: -3 // 2 = -2). Cần adjust:
if prev < 0:
result = -(-prev // num)
else:
result = prev // num
Phân tích
- Time:
O(n)- single pass. - Space:
O(n)stack (worst case all + -). - Không cần recursion hay Shunting-yard vì chỉ 2 mức precedence.
Mở rộng: Basic Calculator III (có dấu ngoặc)
Dùng recursive descent hoặc stack + sign stack. Phức tạp hơn.
Kết luận
Stack method tận dụng tính chất: * / có precedence cao hơn + -, xử lý ngay lập tức. + - delay bằng cách push signed number. Tổng stack = kết quả.