Cấu trúc Stack – Tính giá trị biểu thức Polish Notation

Cấu trúc stack
Stack là một cấu trúc dữ liệu kiểu danh sách (list) đặc biệt có hỗ trợ 2 thao tác trên nó:
– Push(item) để đưa phần tử vào stack. Phần tử mới sẽ luôn nằm ở trên cùng của stack.
– Pop() để lấy phần tử ra khỏi stack. Phần tử lấy ra chính là phần tử nằm trên cùng của stack.
Bạn có thể tưởng tượng stack đơn giản giống như một chồng đĩa xếp lên nhau vậy. Xin mời bạn xem hình minh họa:
Bài toán tính giá trị biểu thức theo ký pháp nghịch đảo Balan
Giả sử bạn cần tính giá trị của một chuỗi biểu thức nhập từ bàn phím thí dụ: 2 + 3 – 4 * ( 5 + 1 ) ^ ( 1 + 1 )
Thông thường, ta tính như sau:
2 + 3 – 4 * ( 5 + 1 ) ^ ( 1 + 1 ) = 5 – 4 * (5 + 1) ^ (1 + 1) = 5 – 4 * 6 ^ 2 = 5 – 4 * 36 = 5 – 144 = -139
Tuy nhiên, việc tính toán này khá phức tạp khi đưa vào máy tính vì ta gặp trở ngại về thứ tự tính toán dựa vào độ ưu tiên của dấu ngoặc và các toán tử.
Vào năm 1920, nhà toán học người Balan, Jan Łukasiewicz giới thiệu phương pháp chuyển đổi biểu thức thường sang dạng ký pháp khác sao cho khi thực hiện tính toán có thể bỏ qua thứ tự ưu tiên toán tử cũng như loại bỏ các dấu ngoặc. Biểu thức trên sau khi được chuyển sang dạng ký pháp Balan được viết lại như sau: 2 3 + 4 5 1 + 1 1 + ^ * –
Như vậy biểu thúc trên sẽ được tính bằng cách dò từ trái qua phải của biểu thức cho đến khi gặp toán tử, ta quay lui lấy 2 toán hạng liền kề với nó rồi thực hiện phép tính, được kết quả bao nhiêu sẽ điền vào chỗ cũ và loại bỏ những thành phần đã được tính đi. Ví dụ:
2 3 + 4 5 1 + 1 1 + ^ * –  ===> duyệt từ trái sang phải, gặp dấu + đầu tiên, lui lại để lấy 2 và 3 ra, thực hiện 2 + 3 = 5, thay 5 vào biểu thức cũ
5 4 5 1 + 1 1 + ^ * –   ===>  tiếp tục duyệt, lại gặp dấu +, quay lại lấy 5 và 1 ra, thực hiện 5 + 1 = 6, thay vào biểu thức cũ
5 4 6 1 1 + ^ * –  ===> 1 + 1 = 2, thay 2 vào
5 4 6 2 ^ * –  ===> 6 ^ 2 = 36, thay 36 vào
5 4 36 * –  ===> 4 * 36 = 144, thay 144 vào
5 144 –  ===> 5 – 144 = -139 (kết quả)
Dùng stack S tính giá trị biểu thức từ chuỗi ký pháp nghịch đảo:
– Duyệt từ trái sang phải chuỗi ký pháp
– Nếu gặp toán hạng thì push vào S
– Nếu gặp toán tử thì pop từ S ra 2 toán hạng, thực hiện tính toán để được kết quả x, Push(x)
Hình minh họa một số bước xử lý:
Tiếp theo, ta tìm hiểu phương pháp biến đổi một biểu thức thông thường thành dạng ký pháp Balan. Một số từ khóa bạn phải làm quen trước khi đi vào thuật toán:
– Tokenize: là việc cắt chuỗi thành các thành phần cơ bản để xử lý. Ví dụ chuỗi “11 + 5 – 12” sẽ được cắt thành các thành phần: 11, +, 5, -, 12
– Token: Mỗi thành phần của một chuỗi sau khi đã tokenize gọi là một token. Một token ở đây có thể là một toán hạng hoặc một toán tử.
Một chuỗi biểu thức phải được tokenize thành list các token trước khi thực hiện thuật toán. Các bước thuật toán như sau:
Khởi tạo stack S để chứa toán tử và ‘(‘
List các token là T
Chuỗi đầu ra là O
pr(o) : là độ ưu tiên của một toán tử
S.top(): là giá trị ở đỉnh stack S
Bước 1: S.Push(‘(‘) và T.Add(‘)’)
Bước 2: Duyệt từng phần tử t của T
Bước 3: Kiểm tra kiểu của t
Bước 3.1: Nếu t là toán hạng => O = O + t
Bước 3.2: Nếu t = ‘(‘ => Push t vào S
Bước 3.3: Nếu t là toán tử:
Bước 3.3.1: Lần lượt xét k = S.top(), Nếu p(k) < p(t) thì O = O + S.pop()
Bước 3.3.2: Push t vào S
Bước 3.4: Nếu t = ‘)’: Lặp cho đến khi S.top() = ‘(‘; Gán O = O + S.pop() (không tính ‘(‘)
No Comments

Post A Comment