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 :
Dưới đây là phần cài đặt :
[You must be registered and logged in to see this link.]
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
Ở đâ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 :
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 :
Cài đặt bằng 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 :
Dưới đây là phần cài đặt bằng C# :
[You must be registered and logged in to see this link.]
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.]
Ở 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.]
using System;
using System.Collections.Generic;
namespace StackDemo2
{
class Program
{
static void Main(string[] args)
{
StackS = new Stack (); //stack dùng để xử lý
int N; //số N (hệ 10) cần chuyển
byte[] coso = { 2, 8 }; //các cơ số cần chuyển
do
{
//nhập N > 0 ở hệ cơ số 10
Console.Write("Nhap N (he 10) : ");
N = int.Parse(Console.ReadLine());
} while (N < 0);
Console.Clear();
//chuyển qua các cơ số : 2, 8
Console.WriteLine("N (10) = {0}", N);
foreach (byte i in coso)
{
int temp = N; //biến tạm, tránh tác động trực tiếp vào N
S.Clear(); //xóa stack
while (temp > 0)
{
S.Push(temp % i); //đẩy phần dư vào stack
temp /= i; //lưu lại phần thương
}
//in ra kết quả
Console.Write("N ({0}) = ", i);
//lấy lần lượt các phần tử ra khỏi stack
while (S.Count > 0)
Console.Write(S.Pop());
Console.WriteLine();
}
Console.ReadLine();
}
}
}
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.
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.]
using System;
using System.Collections.Generic;
namespace StackDemo3
{
class Program
{
static void Main(string[] args)
{
StackS = new Stack (); //stack chứa kết quả
string[] Arr; //mảng chứa toán hạng và toán tử
//Nhập vào biểu thức
Console.Write("Nhap bieu thuc hau to : ");
//Tách chuỗi thành các toán hạng và toán tử
Arr = Console.ReadLine().Replace(" ", " ").Split(' ');
//Duyệt biểu thức
try
{
foreach (string s in Arr)
{
float a = 0, b = 0; //2 biến chứa toán hạng
switch (s)
{
//nếu là các toán tử
case "+":
//lấy 2 số ra khỏi stack
a = S.Pop();
b = S.Pop();
//tính toán và đẩy vào stack
S.Push(a + b);
break;
case "-":
//lấy 2 số ra khỏi stack
//a lấy ra trước nên a là số trừ
a = S.Pop();
b = S.Pop();
//tính toán và đẩy vào stack
S.Push(b - a);
break;
case "*":
//lấy 2 số ra khỏi stack
a = S.Pop();
b = S.Pop();
//tính toán và đẩy vào stack
S.Push(a * b);
break;
case "/":
//lấy 2 số ra khỏi stack
//a lấy ra trước nên a là số chia
a = S.Pop();
b = S.Pop();
//tính toán và đẩy vào stack
S.Push(b / a);
break;
default:
//nếu là toán hạng thì đẩy vào stack
S.Push(int.Parse(s));
break;
}
}
}
catch (Exception)
{
Console.Clear();
Console.WriteLine("Loi trong qua trinh xu ly. Ket thuc chuong trinh.");
Console.ReadLine();
return;
}
//in kết quả
Console.Clear();
if (S.Count > 0) Console.WriteLine("Ket qua : {0}", S.Pop());
Console.ReadLine();
}
}
}
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.]