- Yêu cầu đã học qua cấu trúc dữ liệu stack, queue.
- Mục tiêu: tìm hiểu cách sử dụng cấu trúc dữ liệu để định trị biểu thức
Tại sao chúng ta nên dùng thuật toán Ba Lan ngược để biểu diễn biểu thức khi muốn tính giá trị biểu thức bằng lập trình máy tính?
Khi lập trình, việc để cho máy tính tính giá trị một biểu thức toán học là điều quá đỗi bình thường, nhưng để trình bày làm sao cho máy tính có thể đọc và hiểu được quy trình tính toán đó không phải là điều đơn giản. Trong nhiều ứng dụng [như chương trình vẽ đồ thị hàm số chẳng hạn, trong đó chương trình cho phép người dùng nhập vào hàm số], ta cần phải tính giá trị của một biểu thức được nhập vào từ bàn phím dưới dạng một chuỗi. Với các biểu thức toán học đơn giản [như a+b] thì bạn có thể tự làm bằng các phương pháp tách chuỗi “thủ công”. Nhưng để “giải quyết” các biểu thức có dấu ngoặc, ví dụ như [a+b]*c + [d+e]*f , thì các phương pháp tách chuỗi đơn giản đều không khả thi. Trong tình huống này, ta phải dùng đến Ký Pháp Nghịch Đảo Ba Lan [Reserve Polish Notation – RPN], một thuật toán “kinh điển” trong lĩnh vực trình biên dịch.
Để đơn giản cho việc minh họa, ta giả định rằng chuỗi biểu thức mà ta nhận được từ bàn phím chỉ bao gồm: các dấu mở ngoặc/đóng ngoặc; 4 toán tử cộng, trừ, nhân và chia [+, -, *, /]; các toán hạng đều chỉ là các con số nguyên từ 0 đến 9; không có bất kỳ khoảng trắng nào giữa các ký tự.
Thế nào là ký pháp nghịch đảo Ba Lan?
Cách trình bày biểu thức theo cách thông thường tuy tự nhiên với con người nhưng lại khá “khó chịu” đối với máy tính vì nó không thể hiện một cách tường minh quá trình tính toán để đưa ra giá trị của biểu thức. Để đơn giản hóa quá trình tính toán này, ta phải biến đổi lại biểu thức thông thường về dạng hậu tố – postfix [cách gọi ngắn của thuật ngữ ký pháp nghịch đảo Ba Lan]. Để phân biệt hai dạng biểu diễn biểu thức, ta gọi cách biểu diễn biểu thức theo cách thông thường là trung tố – infix [vì toán tử nằm ở giữa hai toán hạng].
Ký pháp nghịch đảo Ba Lan được phát minh vào khoảng giữa thập kỷ 1950 bởi Charles Hamblin – một triết học gia và khoa học gia máy tính người Úc – dựa theo công trình về ký pháp Ba Lan của nhà Toán học người Ba Lan Jan Łukasiewicz. Hamblin trình bày nghiên cứu của mình tại một hội nghị khoa học vào tháng 6 năm 1957 và chính thức công bố vào năm 1962.
Từ cái tên hậu tố các bạn cũng đoán ra phần nào là theo cách biểu diễn này, các toán tử sẽ được đặt sau các toán hạng. Cụ thể là biểu thức trung tố: 4+5 sẽ được biểu diễn thành 4 5 +.
Quá trình tính toán giá trị của biểu thức hậu tố khá tự nhiên đối với máy tính. Ý tưởng là đọc biểu thức từ trái sang phải, nếu gặp một toán hạng [con số hoặc biến] thì push toán hạng này vào ngăn xếp; nếu gặp toán tử, lấy hai toán hạng ra khỏi ngăn xếp [stack], tính kết quả, đẩy kết quả trở lại ngăn xếp. Khi quá trình kết thúc thì con số cuối cùng còn lại trong ngăn xếp chính là giá trị của biểu thức đó.
Ví dụ: biểu thức trung tố :
5 + [[1 + 2] * 4] + 3
được biểu diễn lại dưới dạng hậu tố là [ta sẽ bàn về thuật toán chuyển đổi từ trung tố sang hậu tố sau]:
5 1 2 + 4 * + 3 +
Bắt đầu tìm hiểu quy trình chuyển đối nghịch đảo Ba Lan. Đối với lập trình, biếu thức ta nhận được sẽ lưu vào chuỗi [strinh chẳng hạn] sau đó viết thêm các hàm nhận biết toán tử và toán hạn để tiến hành đọc và chuyển đổi biểu thức. Quá trình đọc và chuyển đổi sẽ cần ta thao tác với [ngăn xếp và hàng đợi]. Cụ thể là 1 queue sẽ dùng để lưu giữ biểu thức sau khi chuyển xong, và 1 stack đệm [xong quá trình chuyển đổi ta sẽ huỷ nó đi] để lưu các toán tự trong quá trình đọc
Lưu ý: khi ta đọc đọc 1 toán tử [khác “[]”, và ta đang chuẩn bị đưa vào stack] thì sẽ có 2 trường hợp xảy ra:
– toán tử chuẩn bị thêm vào sẽ có độ ưu tiên cao hơn toán tử đầu stack: lúc nào ta đơn giản chỉ push toán tử đó vào stack
– toán tử mới có độ ưu tiên thấp hơn toán tử đầu stack: lúc nào ta sẽ lấy lần lượt toán tử từ đầu stack ra [cho đến khi hết stack hoặc gặp “[” ] rồi thêm chúng vào queue, sau đó nhớ push trả lại “[” và push toán tử mới vào.
Không còn kí tự nào nữa ta sẽ lấy hết những toán tử còn lại trong stack ra và cho vào queue, sau đó xoá bỏ stack. Ta sẽ được 1 biểu thức nghịch đảo Ba Lan: 5 1 2 + 4 * + 3 +
Không khác gì ví dụ ở trên đúng không nào? Giờ đây ta đã có 1 hàng đợi lưu trữ biểu thức sau khi chuyển đổi, việc còn lại là tính toán để ra định trị của biểu thức
Tại sao phương pháp nghịch đảo Ba Lan lại giúp cho máy tính hiểu được biểu thức?
Máy tính cũng chỉ là một cái máy, quá trình lập trình ta sẽ cần trừu tượng quá quy trình xử lý một cách rõ ràng [trong khi con người đã có thể bỏ qua bước này, giống như bạn có thể đọc 1 biểu thức 1 lần là có thể biết được cặp số hạng nào cần tính trước cái nào phải tính sau. Nhưng máy tính muốn biết được điều đó ta phải trừu tượng quá trình đó bằng sự kết hợp giữa ngăn xếp và hàng đợi]. Chính sự kết hợp 1 cách khéo léo của lập trình viên trong việc sử dụng thuật toán nghịch đảo Ba Lan, kiến thức tính biểu thức [tiểu học có học rồi], kĩ năng thao tác với hàng đợi và ngăn xếp, là điều mà sẽ giúp cho máy tính hiểu được nó phải làm gì với biểu thức.
Bây giờ hãy quay lại với ví dụ trên:
5 + [[1 + 2] * 4] + 3 [Biểu thức bình thường]
5 1 2 + 4 * + 3 + [Biểu thức sau khi nghịch đảo Ba Lan]
Tới lúc này, tôi đang giả sử rằng chúng ta đã lập trình xong mã nguồn để chuyển từ biểu thức thường sang dạng nghịch đảo Ba Lan rồi. Việc ta cần làm bây giờ là cho bạn thấy được sự “kết hợp khéo léo” ở bên trên giúp ích như thế nào.
Ta tiến hành đọc biểu thức sau khi biến đổi theo hình thức trừu tượng hoá của hàng đợi đó là lấy dữ liệu theo nguyên tắc FIFO [first in last out]. Ta sẽ tạo thêm 1 stack mới để các toán hạng và kết quả sau mỗi lần tính liệu lấy ra từ queue biểu thức.
Hết dữ liệu trong Queue chứa biểu thức nghịch đảo, ta xoá queue, lấy kết quả cuối cùng có được tự stack ra ngoài [muốn làm gì với nó thì tuỳ yêu cầu tiếp theo] rồi xoá stack đi, kết thúc quá trình tính định trị biểu thức
Mã nguồn ví dụ cho thuật toán này sẽ được cập nhật sớm nhất [link]
Tài liệu tham khảo thêm:
– Sách Kĩ Thuật Lập Trình [Trần Đan Thư, Nguyễn Thanh Phương, Đinh Bá Tiến, Đặng Bình Phương, Trần Minh Triết] trường đại học Khoa Học Tự Nhiên TPHCM
– Bài viết đã tham khảo và thêm 1 số nội dung từ web [link].
Ứng dụng ngăn xếp [Stack] và hàng đợi [Queue] để viết chương trình biến đổi biểu thức trung tố thành tiền tố và hậu tố.
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây [530.04 KB, 25 trang ]
Bài tiểu luận môn: Cấu trúc dữ liệu và giải thuật
Mục lục
Mục lục...................................................................................................................... 1
Phần I: Mở đầu .....................................................................................................2
I. Giới thiệu đề tài ..................................................................................................... 2
II. Mục đích yêu cầu của đề bài ................................................................................ 2
1. Mục đích ......................................................................................................... 2
2. Yêu cầu ........................................................................................................... 3
III. Phương pháp nghiên cứu..................................................................................... 3
Phần II: Nội dung .................................................................................................3
I. Ngăn xếp [Stack] ................................................................................................... 3
II. Hàng đợi [Queue] ................................................................................................. 4
III. Ứng dụng của Stack và Queue trong ký pháp Ba Lan ........................................ 4
1. Khái niệm: ..................................................................................................... 4
2. Chuyển đổi dạng Infix[trung tố] sang Postfix[hậu tố] .................................. 5
3. Tính giá trị biểu thức dạng Postfix[hậu tố] .................................................... 6
4. Chuyển đổi dạng Infix[trung tố] sang Prefix[tiền tố]..................................... 7
5. Tình giá trị biểu thức dạng Prefix[tiền tố]...................................................... 8
IV. Chương trình đầy đủ ........................................................................................... 9
Phần III: Kết luận ...............................................................................................24
TÀI LIỆU THAM KHẢO.....................................................................................25
GVHD: Trịnh Thị Phú
Sinh viên thực hiện: Hoàng Năng Hưng
1
Bài tiểu luận môn: Cấu trúc dữ liệu và giải thuật
Phần I: Mở đầu
I. Giới thiệu đề tài
Trong khoa học máy tính, cấu trúc dữ liệu là cách lưu dữ liệu trong máy
tính sao cho nó có thể được sử dụng một cách hiệu quả. Thông thường, một cấu
trúc dữ liệu được chọn cẩn thận sẽ cho phép thực hiện thuật toán hiệu quả hơn.
Việc chọn cấu trúc dữ liệu thường bắt đầu từ chọn một cấu trúc dữ liệu trừu
tượng. Một cấu trúc dữ liệu được thiết kế tốt cho phép thực hiện nhiều phép toán,
sử dụng càng ít tài nguyên, thời gian xử lý và không gian bộ nhớ càng tốt. Các cấu
trúc dữ liệu được triển khai bằng cách sử dụng các kiểu dữ liệu, các tham chiếu và
các phép toán trên đó được cung cấp bởi một ngôn ngữ lập trình.
Trong đó nổi trội lên là hai cấu trúc dữ liệu đó là Stack [ngăn xếp] và Queue
[hàng đợi]. Stack và Queue có ứng dụng rất nhiều kể cả trong thuật toán lẫn trong
thực tế. Hàng ngày chúng ta thường xuyên làm việc và tiếp xúc với các biểu thức,
toán hạng, toán tử… và máy tính cũng vậy. Tuy nhiên máy tính không thể nào hiểu
được ngôn ngữ và cách viết của con người, vì vậy để máy tính hiểu được các biểu
thức thì chúng ta phải chuyển chúng về một dạng mà máy tính có thể thực hiện
được. Vì vậy em xin chọn đề tài “Ứng dụng ngăn xếp [Stack] và hàng đợi [Queue]
để viết chương trình biến đổi biểu thức trung tố thành tiền tố và hậu tố” để làm bài
tiểu luận.
II. Mục đích yêu cầu của đề bài
1. Mục đích
Đề tài này giúp em củng cố, nâng cao kiến thức về môn học cấu trúc dữ liệu
và giải thuật. Từ đó hiểu sâu hơn và vận dụng vào trong các bài toán số liệu thực tế
đồng thời thông qua việc làm đề tài này giúp em biết được các phương pháp
nghiên cứu một vấn đề nhỏ nào đó.
GVHD: Trịnh Thị Phú
Sinh viên thực hiện: Hoàng Năng Hưng
2
Bài tiểu luận môn: Cấu trúc dữ liệu và giải thuật
2. Yêu cầu
Dùng ngôn ngữ lập trình C/C++ để cài đặt chương trình. Với dữ liệu được
nhập vào từ bàn phím.
III. Phương pháp nghiên cứu
+ Tham khảo tài liệu: cấu trúc dữ liệu và giải thuật, trên mạng…
+ Tìm hiểu thực tiễn, thực tế, quy cách, nhu cầu của bài toán.
+ Xin ý kiến, hướng dẫn của giáo viên hướng dẫn.
Phần II: Nội dung
I. Ngăn xếp [Stack]
Ngăn xếp [Stack] là một danh sách có thứ tự mà phép chèn và xóa được
thực hiện tại đầu cuối của danh sách và người ta gọi đầu cuối này là đỉnh
[top] của stack. Với nguyên tắc vào sau ra trước, danh sách kiểu LIFO [last
- in - first - out].
Có 2 cách lưu trữ Stack:
+ Bằng mảng.
+ Bằng danh sách liên kết.
Các thao tác cơ bản trên Stack:
Push: Đưa một phần tử vào đỉnh của Stack.
Pop: Lấy từ đỉnh của Stack một phần tử.
Peek: Xem đỉnh của Stack chứa nội dung là gì?
Một số ứng dụng của Stack:
Ứng dụng trực tiếp:
Ứng dụng nổi bật của Stack là Stack cho chương trình sử dụng Stack để gọi
hàm.
Trong trình duyệt WEB, các trang đã xem được lưu trong
stack.
GVHD: Trịnh Thị Phú
Sinh viên thực hiện: Hoàng Năng Hưng
3
Bài tiểu luận môn: Cấu trúc dữ liệu và giải thuật
Trong trình soạn thảo văn bản, thao tác Undo được lưu
trong stack.
Ứng dụng gián tiếp:
Cấu trúc dữ liệu bổ trợ cho thuật toán khác.
Một thành phần của cấu trúc dữ liệu khác.
II. Hàng đợi [Queue]
Hàng đợi là kiểu danh sách tuyến tính mà phép bổ sung được thực hiện ở 1
đầu, gọi là lối sau [rear] và phép loại bỏ thực hiện ở 1 đầu khác gọi là lối
trước [front]. Nguyên tắc vào trước ra trước, danh sách kiểu FIFO [first - in
- first - out].
Có 2 cách lưu trữ tương tự như Stack:
+ Bằng mảng.
+ Bằng danh sách liên kết.
Ứng dụng của Queue
Ứng dụng trực tiếp
Danh sách hàng đợi.
Quản lý truy cập tới các tài nguyên dùng chung [ví dụ máy in].
Multiprogramming.
Ứng dụng gián tiếp
Cấu trúc dữ liệu phụ trợ cho các thuật toán.
Một phần của CTDL khác.
III. Ứng dụng của Stack và Queue trong ký pháp Ba Lan
1. Khái niệm:
Prefix: Biểu thức tiền tố được biểu diễn bằng cách đặt toán tử lên trước các
toán hạng. Cách biểu diễn này còn được biết đến với tên gọi “ký pháp Ba Lan” do
GVHD: Trịnh Thị Phú
Sinh viên thực hiện: Hoàng Năng Hưng
4
Bài tiểu luận môn: Cấu trúc dữ liệu và giải thuật
nhà toán học Ba Lan Jan Łukasiewicz phát minh năm 1920. Với cách biểu diễn
này, thay vì viết x + y như dạng trung tố, ta sẽ viết + x y. Tùy theo độ ưu tiên của
toán tử mà chúng sẽ được sắp xếp khác nhau, bạn có thể xem một số ví dụ ở phía
sau phần giới thiệu này.
Postfix: Ngược lại với cách Prefix, biểu thức hậu tố tức là các toán tử sẽ
được đặt sau các toán hạng. Cách biểu diễn này được gọi là “ký pháp nghịch đảo
Ba Lan” hoặc được viết tắt là RPN[Reverse Polish notation], được phát minh vào
khoảng giữa thập kỷ 1950 bởi một triết học gia và nhà khoa học máy tính Charles
Hamblin người Úc.
Ví dụ:
2. Chuyển đổi dạng Infix[trung tố] sang Postfix[hậu tố]
Thuật toán:
Bước 1: Đọc một thành phần của biểu thức E [dạng Infix biểu diễn
bằng xâu, đọc từ trái qua phải]. Giả sử thành phần đọc được là x
Bước 1.1: Nếu x là toán hạng thì viết nó vào bên phải biểu thức E1 [xâu
lưu
kết quả của Postfix]
Bước 1.2: Nếu x là dấu ‘[’ thì đẩy nó vào Stack.
Bước 1.3: Nếu x là một trong các phép toán +, -, *, / thì
Bước 1.3.1: Xét phần tử y ở đỉnh Stack.
Bước 1.3.2: Nếu Pri[y] >= Pri[x] là một phép toán thì loại y ra khỏi
Stack và viết y vào bên phải của E1 và quay lại bước 1.3.1
Bước 1.3.3: Nếu Pri[y] < Pri[x] thì đẩy x vào Stack.
Bước 1.4: Nếu x là dấu ‘]’ thì
GVHD: Trịnh Thị Phú
Sinh viên thực hiện: Hoàng Năng Hưng
5
Bài tiểu luận môn: Cấu trúc dữ liệu và giải thuật
Bước 1.4.1: Xét phần tử y ở đầu của Stack.
Bước 1.4.2: y là phép toán thì loại y ra khỏi Stack, viết y vào bên
phải E1 và quay trở lại 1.4.1
Bước 1.4.3: Nếu y là dấu ‘[’ loại y ra khỏi Stack.
Bước 2: Lập lại bước 1 cho đến khi toàn bộ biểu thức E được đọc qua
Bước 3: Loại phần tử ở đỉnh Stack và viết nó vào bên phải E1. Lặp lại bước này
cho đến khi Stack rỗng.
Bước 4: Tính giá trị của biểu thức dưới dạng hậu tố
Ví dụ: Cho biểu thức: E = a * [b + c] – d / e
3. Tính giá trị biểu thức dạng Postfix[hậu tố]
Thuật toán:
Bước 1: Đọc lần lượt các phần tử của biểu thức E1 [từ trái qua phải]. Nếu gặp toán
hạng thì đẩy nó vào Stack. Nếu gặp phép toán thì lấy hai phần tử liên tiếp trong
Stack thực hiện phép toán, kết quả được đẩy vào trong Stack.
Bước 2: Lập lại bước 1 cho đến khi hết tất cả các phần tử trong biểu thức E1. lúc
đó đỉnh của Stack chứa giá trị của
biểu thức cần tính
Bước 3: Kết thúc.
GVHD: Trịnh Thị Phú
Sinh viên thực hiện: Hoàng Năng Hưng
6
Bài tiểu luận môn: Cấu trúc dữ liệu và giải thuật
Ví dụ: tính giá trị của biểu thức sau: 4 5 + 2 3 + * 6 + 8 7 + /
Giải thuật được trình bày như sau:
4. Chuyển đổi dạng Infix[trung tố] sang Prefix[tiền tố]
Thuật toán:
Ý tưởng: Sử dụng Stack và Queue và Stackkq.
Bước 1: Đọc một thành phần của biểu thức E [dạng Infix biểu diễn bằng xâu, đọc
từ phải qua trái]. Giả sử thành phần đọc được là x:
Bước 1.1: Nếu x là toán hạng thì đưa nó vào Queue.
Bước 1.2: Nếu x là dấu ‘]’ thì đẩy nó vào Stack.
Bước 1.3: Nếu x là một trong các phép toán +, -, *, / thì:
Bước 1.3.1: Kiểm tra xem stack có rỗng không? Nếu rỗng, đẩy
vào Stack, nếu không rỗng, sang bước 1.3.2.
Bước 1.3.2: Lấy phần tử y ở đỉnh Stack.
Bước 1.3.3: Nếu Pre[y]>=Pre[x], đưa tất cả các phần tử trong
Queue vào Stackkq, đưa y vào Stackkq, đưa x vào Stack.
Bước 1.3.4: Nếu Pre[y]