224. Basic calculator

Problem

Viết thuật toán tính toán cơ bản cho máy tính

Approach

💡

Stack: Lưu trữ kết quả và dấu trước “() để xử lý biểu thức con trong ngoặc

Sign: Theo dõi dấu của các số tiếp theo (+ / - )

Xử lý từng ký tự: Duyệt qua từng ký tự trong chuỗi để xây dựng số, áp dụng dấu và quản lý stack khi gặp dấu ngoặc

Khởi tạo

stack: Lưu các cặp (result, sign) khi gặp dấu ngoặc

result: Lưu kết quả tạm thời

sign: Dấu hiện tại (mặc định là 1 (+))

num: xây dựng số từ các ký tự liên tiếp

Duyệt từng ký tự

Bỏ qua khoảng trắng

Nếu là số: Cập nhật num

Nếu là toán tử (+, -) hoặc dấu ngoặc:

Cập nhật result với num đã xây dựng

Xử lý toán tử hoặc dấu ngoặc:

+ / - : Đặt lại sign

(: Đẩy result và sign vào stack, reset result và sign

): Lấy giá trị từ stack và cập nhật result

Cộng số cuối cùng sau khi duyệt xong chuỗi

Time and space complexity

TC: O(n)

SC: O(n

Solution

typescripttypescript

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}

💡

Tóm tắt

Khi gặp ( , lưu trạng thái hiện tại vào stack để xử lý biểu thức con ngoặc

Khi gặp ) , lấy lại trạng thái trước đó và cộng/ trừ kết quả trong ngoặc vào

Đọc số liên tiếp để xử lý các số nhiều chữ số

💡

Tại sao lại tính res += sign * curr_num:

Lý do phải cộng bên ngoài vòng lặp

Trong quá trình duyệt chuỗi, mỗi khi gặp một số, bạn thường chỉ lưu tạm số đó vào biến curr_num (hoặc tương tự)

Khi gặp dấu +, - 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 theo

Tuy nhiên, số cuối cùng trong chuỗi có thể không kết thúc bằng một toán tử hoặc dấu ngoặc, mà kết thúc luôn ở cuối chuỗi. Nếu bạn không cộng nốt số cuối cùng này vào res sau khi vòng lặp kết thúc, kết quả sẽ bị thiếu

Ví dụ

Biểu thức: "1 + 2"

Khi duyệt đến ký tự cuối cùng (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.

Do đó, sau vòng lặp, bạn phải cộng nốt: res += sign * curr_num.

💡

Tại sao lại tính result = prev_result + prev_sign * result;

Khi gặp dấu ngoặc đóng ), 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:

Lấy lại prev_sign và prev_result từ stack.

Biểu thức trong ngoặc phải được nhân với dấu ngay trước ngoặc (có thể là dấu trừ, ví dụ: (1+2)).

Sau đó cộng vào kết quả trước dấu ngoặc.

Ví dụ minh họa:

Với biểu thức 2 - (3 + 4), khi tới dấu ), ta có:

prev_result = 2

prev_sign = -1

result = 7 (kết quả trong ngoặc)

=> Áp dụng: result = 2 + (-1) * 7 = -5

Loading content...

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}