Vui lòng đọc hiểu đề trước khi đọc bài viết này tại đây:
https://leetcode.com/problems/evaluate-reverse-polish-notation/description/
Table of Contents
1. Cách tiếp cận vấn đề
Bài toán đưa cho ta 1 chuỗi ký pháp Ba Lan ngược (Reverse_Polish_notation) và yêu cầu ta tính toán giá trị cho chuỗi ký pháp đó. Ví dụ: với mảng tokens = ["2","1","+","4","*"] tương ứng với ký pháp Ba Lan ngược là "2 1 + 4 *". Ta cần biến đổi nó thành "(2 + 1) * 4" và tính toán kết quả với giá trị cuối cùng là 12.
Quan sát ký pháp Ba Lan ngược thì ta thấy mỗi khi gặp một phép tính nào đó thì trước đó cần phải tồn tại 1 cặp số thì mới kết hợp với phép tính đó được. Và kết quả tính toán của cặp số đó sẽ là x, và x cũng chính là 1 phần của cặp số mới để thực hiện phép tính tiếp theo:
- Khi gặp dấu +, ta cần lấy ra được 2 số "2" và "1" và tính toán được kết quả là 3
- Khi gặp dấu *, ta cần lấy ra được số "3" đã tính ở bước trên và số "4" đã có sẵn ở input, sau đó tính toán và trả được kết quả cuối cùng là 12.
2. Solution & Phân Tích
Như đã đề cập ở trên, cấu trúc dữ liệu ngăn xếp sẽ là phù hợp nhất để giải bài toán này, ta sẽ duyệt qua từng token, nếu token đó:
- Là một số nguyên, ta sẽ push số nguyên đó vào stack
- Là một trong 4 dấu "+", "-", "*", "/"
- Ta sẽ pop từ stack ra 2 số nguyên lần lượt là b và a (số đầu pop được là b còn số sau pop được là a), từ đó ta áp dụng phép tính lên 2 số a và b đó được kết quả là số c.
- Sau cùng push số c vào stack để tiếp tục kết hợp với số nguyên khác hoặc cũng có thể c chính là kết quả cuối cùng.
Sau khi duyệt qua tất cả các token, số còn lại trong stack chính là kết quả của chuỗi ký pháp Ba Lan ngược.
Time-Complexity: O(n)
Space-Complexity: O(n)
Với n là số lượng các token trong mảng input.
3. Code
