224. Basic calculator
Tags:
Hard
Skills:
Stack
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Viết thuật toán tính toán cơ bản cho máy tính
Approach
Time and space complexity
Solution
1function calculate(s: string): number {
2 let result = 0;
3 let current_number = 0;
4 let sign = 1;
5 const stack: number[] = []
6
7 for (const char of s) {
8 if (char === ' ') {
9 continue;
10 } else if (char >= '0' && char <= '9') {
11 current_number = current_number * 10 + parseInt(char, 10);
12 } else {
13 result += sign * current_number;
14 current_number = 0;
15
16 if (char === '+') {
17 sign = 1;
18 } else if (char === '-') {
19 sign = -1;
20 } else if (char === '(') {
21 stack.push(result);
22 stack.push(sign);
23 result = 0;
24 sign = 1;
25 } else if (char === ')') {
26 const prev_sign = stack.pop();
27 const prev_result = stack.pop();
28
29 result = prev_result + prev_sign * result;
30 }
31 }
32 }
33 result += sign * current_number;
34 return result;
35}( , lưu trạng thái hiện tại vào stack để xử lý biểu thức con ngoặc) , lấy lại trạng thái trước đó và cộng/ trừ kết quả trong ngoặc vàoLý do phải cộng bên ngoài vòng lặp
curr_num (hoặc tương tự)+, - hoặc dấu ngoặc, bạn mới thực sự cộng/trừ số vừa đọc vào tổng res += sign * curr_num sau đó reset curr_num về 0 để tiếp tục đọc số tiếp theores sau khi vòng lặp kết thúc, kết quả sẽ bị thiếuVí dụ
Biểu thức: "1 + 2"
2), vòng lặp kết thúc mà chưa gặp dấu +, hay ngoặc để cộng 2 vào res.res += sign * curr_num.result = prev_result + prev_sign * result;), bạn cần "thoát" khỏi ngoặc và kết hợp kết quả vừa tính với phần bên ngoài:prev_sign và prev_result từ stack.(1+2)).Ví dụ minh họa:
Với biểu thức 2 - (3 + 4), khi tới dấu ), ta có:
prev_result = 2prev_sign = -1result = 7 (kết quả trong ngoặc)=> Áp dụng: result = 2 + (-1) * 7 = -5