PHẦN 2 : ỨNG DỤNG CỦA STACK | Huynh Minh Khoa Is Weblog

Trang chủ » Chuyển Hệ 10 Sang Hệ 2 Stack » PHẦN 2 : ỨNG DỤNG CỦA STACK | Huynh Minh Khoa Is Weblog

Có thể bạn quan tâm

Ở 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 :

UngDungStack_1

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.

UngDungStack_2

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

Code

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

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ố.

UngDungStack_3

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.

UngDungStack_4

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

Code

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

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 : Download

Share this:

  • Facebook
  • X
  • Reddit
Like Loading...

Từ khóa » Chuyển Hệ 10 Sang Hệ 2 Stack