PHẦN 2 : ỨNG DỤNG CỦA STACK

Ở phần 1, chúng ta đã tìm hiểu về
Stack và 2 phương pháp cài đặt trong C#. Trong phần này, chúng ta sẽ tìm
hiểu về các ứng dụng của Stack thông qua 2 bài toán đơn giản : đổi cơ
số và tính toán biểu thức hậu tố. Đây là hai ví dụ điển hình nhất cho
việc sử dụng Stack.

Để tiện cho việc minh họa và khỏi mất
công cài đặt lại, ở đây tôi sẽ sử dụng lớp Stack với kiểu Generic có sẵn
của C#. Lớp này có đầy đủ các thao tác cơ bản trên Stack.

1. Bài toán đổi cơ số

Cho số N ở hệ cơ số 10. Đổi số N ra các hệ cơ số : nhị phân, bát phân và thập lục phân. Bài toán chỉ có bấy nhiêu, rất đơn giản. Trước tiên, chúng ta sẽ xem lại quy tắc đổi cơ số trong tin học.




a. Quy tắc đổi cơ số

Muốn chuyển một số N ở hệ thập phân (10) sang hệ cơ số k, ta làm như sau :
lấy N chia cho k, được thương Q và phần dư R. Ghi lại phần dư R theo
thứ tự từ trên xuống. Tiếp tục lấy Q chia cho k như bước trên, lặp lại
cho đến khi Q = 0. Đọc các phần dư R theo thứ tự từ dưới lên, ta sẽ được
kết quả cần tìm.

Dưới đây là sơ đồ minh họa cho việc chuyển N từ hệ 10 sang hệ 2 :



b. Cài đặt bài toán

Để giải quyết bài toán, ta có thể dùng
nhiều cách như : vòng lặp, đệ quy,... Ở đây, tôi sẽ minh họa việc
chuyển cơ số 10 sang 2 bằng Stack.

Ý tưởng : Stack là
cấu trúc dữ liệu truy xuất theo nguyên lý LIFO, nghĩa là vào sau ra
trước. Một dãy các phần tử đi vào stack theo một thứ tự khi được lấy ra
khỏi stack sẽ theo thứ tự ngược lại.

Quá trình đổi cơ số bằng Stack :

• B1. Lấy N chia cho k, được thương Q và đẩy phần dư R vào Stack.
  
• B2. Gán Q cho N.
  
• B3. Lặp lại B1, B2 cho đến khi N=0
  
• B4. Lấy các phần tử R ra khỏi stack cho đến khi stack rỗng.
  

Dưới đây là phần cài đặt :

[You must be registered and logged in to see this link.]

1. 
   using System;
   
2. 
   using System.Collections.Generic;
   
3. 
   
   
4. 
   namespace StackDemo2
   
5. 
   {
   
6. 
   class Program
   
7. 
   {
   
8. 
   static void Main(string[] args)
   
9. 
   {
   
10. 
    Stack S = new Stack(); //stack dùng để xử lý
    
11. 
    int N; //số N (hệ 10) cần chuyển
    
12. 
    byte[] coso = { 2, 8 }; //các cơ số cần chuyển
    
13. 
    do
    
14. 
    {
    
15. 
    //nhập N > 0 ở hệ cơ số 10
    
16. 
    Console.Write("Nhap N (he 10) : ");
    
17. 
    N = int.Parse(Console.ReadLine());
    
18. 
    } while (N < 0);
    
19. 
    Console.Clear();
    
20. 
    //chuyển qua các cơ số : 2, 8
    
21. 
    Console.WriteLine("N (10) = {0}", N);
    
22. 
    foreach (byte i in coso)
    
23. 
    {
    
24. 
    int temp = N; //biến tạm, tránh tác động trực tiếp vào N
    
25. 
    S.Clear(); //xóa stack
    
26. 
    while (temp > 0)
    
27. 
    {
    
28. 
    S.Push(temp % i); //đẩy phần dư vào stack
    
29. 
    temp /= i; //lưu lại phần thương
    
30. 
    }
    
31. 
    //in ra kết quả
    
32. 
    Console.Write("N ({0}) = ", i);
    
33. 
    //lấy lần lượt các phần tử ra khỏi stack
    
34. 
    while (S.Count > 0)
    
35. 
    Console.Write(S.Pop());
    
36. 
    Console.WriteLine();
    
37. 
    }
    
38. 
    Console.ReadLine();
    
39. 
    }
    
40. 
    }
    
41. 
    }
    

2. Bài toán tính giá trị của biểu thức hậu tố

Một biểu thức toán học gồm 2 phần : toán tử và các toán hạng

• Toán tử có thể là các phép tính : +, -, *, / (toán tử 2 ngôi) hay lấy căn bậc 2, bình phương (toán tử 1 ngôi),...
  
• Toán hạng là các số bất kỳ : số thực, số nguyên, hữu tỷ,...
  

Ở đây, tôi chỉ xét các biểu thức bao gồm các toán tử hai ngôi. Bạn có thể mở rộng bài toán ra với các toán tử một ngôi.

Một biểu thức toán học có thể ở 3 dạng :

• Tiền tố (Prefix) : toán tử luôn nằm trước 2 toán hạng của nó và không sử dụng dấu ngoặc.
  
• Trung tố (Infix) : toán tử luôn nằm giữa 2 toán hạng của nó. Có sử dụng dấu ngoặc để gom nhóm các toán hạng.
  
• Hậu tố (Postfix) : toán tử nằm sau 2 toán hạng của nó, cũng không có dấu ngoặc.
  

Các biểu thức mà chúng ta vẫn thường thấy trong toán học chính là các biểu thức trung tố.



Việc tính toán các biểu thức trung tố
trên máy tính không đơn giản do có các dấu ngoặc. Vì vậy để tính các
biểu thức loại này, ta chuyển chúng sang dạng hậu tố. Việc tính toán ở
dạng hậu tố đơn giản hơn nhiều.

VD : cho biểu thức
trung tố 3 * ((5 - 2) * (7 + 1) - 6) --> dạng hậu tố là : 3 5 2 - 7 1
+ * 6 - * . Ta tính biểu thức này như sau :

• Toán tử - nằm ngay sau 2 toán hạng 5 và 2 nên lấy 5 - 2 = 3, lưu kết quả 3
  
• Toán tử + nằm ngay sau 2 toán hạng 7 và 1 nên lấy 7 + 1 = 8, lưu kết quả 8.
  
• Toán tử nhân (*) nằm ngay sau 2 kết quả vừa lưu nên lấy 3 * 8 = 24, lưu kết quả 24.
  
• Toán tử - nằm ngay sau toán hạng 6 và kết quả vừa lưu nên lấy 24 - 6 = 18.
  
• Toán tử nhân nằm ngay sau kết quả vừa lưu và toán hạng 3 nên lấy 18 * 3 = 54 là kết quả cuối củng của biểu thức.
  

Cài đặt bằng Stack :

• Duyệt biểu thức từ trái sang phải :
  
  
  
  • Khi gặp toán hạng, ta đẩy vào Stack
    
  • Khi gặp toán tử, ta lấy 2 toán hạng trên cùng trong Stack ra và thực hiện phép toán. Đẩy kết quả vào Stack.
    
  
  


• Sau khi duyệt xong, phần tử còn lại trong Stack chính là giá trị của biểu thức
  

VD : với biểu thức hậu tố ở trên, ta tính toán trên Stack như sau :

• Duyệt từ trái qua phải, gặp các toán hạng 3, 5, 2 --> đưa vào stack :
  
• Duyệt tiếp, gặp toán tử trừ (-) --> lấy 2 toán hạng trên cùng là 5 và 2 ra, thực hiện 5 - 2 = 3. Đẩy 3 vào stack :
  
• Duyệt tiếp, gặp 2 toán hạng 7, 1 --> đưa vào stack :
  
• Duyệt tiếp, gặp toán tử cộng (+) --> Lấy 7 và 1 ra, thực hiện 7 + 1 = 8. Đẩy 8 vào stack :
  
• Duyệt tiếp, gặp toán tử nhân (*) --> lấy 3 và 8 ra, thực hiện 3 * 8 = 24. Đẩy 24 vào stack :
  
• Duyệt tiếp, gặp toán hạng 6 --> cho vào stack :
  
• Duyệt tiếp, gặp toán tử trừ (-) --> lấy 24 và 6 ra, thực hiện 24 - 6 = 18. Đẩy 18 vào stack :
  
• Duyệt tiếp, gặp toán tử nhân (*) --> lấy 3 và 18 ra, thực hiện 3 * 18 = 54. Đẩy vào stack :
  
• Hết biểu thức, lấy kết quả cuối cùng trong stack ra. Kết quả : 54.
  

Dưới đây là phần cài đặt bằng C# :


[You must be registered and logged in to see this link.]

1. 
   using System;
   
2. 
   using System.Collections.Generic;
   
3. 
   
   
4. 
   namespace StackDemo3
   
5. 
   {
   
6. 
   class Program
   
7. 
   {
   
8. 
   static void Main(string[] args)
   
9. 
   {
   
10. 
    
    
11. 
    Stack S = new Stack(); //stack chứa kết quả
    
12. 
    string[] Arr; //mảng chứa toán hạng và toán tử
    
13. 
    //Nhập vào biểu thức
    
14. 
    Console.Write("Nhap bieu thuc hau to : ");
    
15. 
    //Tách chuỗi thành các toán hạng và toán tử
    
16. 
    Arr = Console.ReadLine().Replace(" ", " ").Split(' ');
    
17. 
    //Duyệt biểu thức
    
18. 
    try
    
19. 
    {
    
20. 
    foreach (string s in Arr)
    
21. 
    {
    
22. 
    float a = 0, b = 0; //2 biến chứa toán hạng
    
23. 
    switch (s)
    
24. 
    {
    
25. 
    //nếu là các toán tử
    
26. 
    case "+":
    
27. 
    //lấy 2 số ra khỏi stack
    
28. 
    a = S.Pop();
    
29. 
    b = S.Pop();
    
30. 
    //tính toán và đẩy vào stack
    
31. 
    S.Push(a + b);
    
32. 
    break;
    
33. 
    case "-":
    
34. 
    //lấy 2 số ra khỏi stack
    
35. 
    //a lấy ra trước nên a là số trừ
    
36. 
    a = S.Pop();
    
37. 
    b = S.Pop();
    
38. 
    //tính toán và đẩy vào stack
    
39. 
    S.Push(b - a);
    
40. 
    break;
    
41. 
    case "*":
    
42. 
    //lấy 2 số ra khỏi stack
    
43. 
    a = S.Pop();
    
44. 
    b = S.Pop();
    
45. 
    //tính toán và đẩy vào stack
    
46. 
    S.Push(a * b);
    
47. 
    break;
    
48. 
    case "/":
    
49. 
    //lấy 2 số ra khỏi stack
    
50. 
    //a lấy ra trước nên a là số chia
    
51. 
    a = S.Pop();
    
52. 
    b = S.Pop();
    
53. 
    //tính toán và đẩy vào stack
    
54. 
    S.Push(b / a);
    
55. 
    break;
    
56. 
    default:
    
57. 
    //nếu là toán hạng thì đẩy vào stack
    
58. 
    S.Push(int.Parse(s));
    
59. 
    break;
    
60. 
    }
    
61. 
    }
    
62. 
    }
    
63. 
    catch (Exception)
    
64. 
    {
    
65. 
    Console.Clear();
    
66. 
    Console.WriteLine("Loi trong qua trinh xu ly. Ket thuc chuong trinh.");
    
67. 
    Console.ReadLine();
    
68. 
    return;
    
69. 
    }
    
70. 
    //in kết quả
    
71. 
    Console.Clear();
    
72. 
    if (S.Count > 0) Console.WriteLine("Ket qua : {0}", S.Pop());
    
73. 
    Console.ReadLine();
    
74. 
    }
    
75. 
    }
    
76. 
    }
    

Qua bài viết, bạn đã thấy được hai ứng
dụng điển hình nhất của Stack. Ngoài ra stack còn được dùng để chuyển
một biểu thức trung tố sang hậu tố cùng nhiều ứng dụng khác.

Project mẫu : [You must be registered and logged in to see this link.]