Bài tiểu luận: Ứ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ài ti u lu n môn: C u trúc d li u và gi

ậ i thu t

ụ ụ M c l c

ở ầ

ầ

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 đ ữ ệ ượ ch n c n th n s cho phép th c hi n thu t toán hi u qu c ả

ệ ườ ắ ầ ừ ọ ộ ấ ữ ệ ọ ấ ơ 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 t k ự 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 ự ế àng ngày chúng ta th . H ệ 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 đ ế ệ ượ Vì v y em xin ch n đ tài “ ng d ng ngăn x p ọ c.

ự

ư

ệ

ị

GVHD: Tr nh Th Phú Sinh vê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

ể ế ươ ứ ế ể ổ ố ợ (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 đó.

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

ữ ệ ệ ả ấ ả ậ ạ i thu t, trên m ng… + Tham kh o tài li u: c u trúc d li u và gi

ự ễ ự ế ể ầ ủ + 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)

(cid:0) 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).

(cid:0) ữ ư Có 2 cách l u tr Stack:

ự

ư

ệ

ị

GVHD: Tr nh Th Phú Sinh vê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

ằ ả + B ng m ng.

ế ằ + B ng danh sách liên k t.

(cid:0) ơ ả 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ì?

(cid:0) 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.

ả ả ạ ượ ư 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)

(cid:0) 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).

(cid:0) ữ ươ ư ự ư Có 2 cách l u tr t ng t nh Stack:

ằ ả + B ng m ng.

ư

ự

ệ

ị

GVHD: Tr nh Th Phú Sinh vê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

ế ằ + B ng danh sách liên k t.

(cid:0) Ứ ụ ủ ng d ng c a Queue

Ứ ụ ng d ng t ự ế r 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 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 i v i cách Prefix, bi u th c h u t c l 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 c vi ế ắ t t t là RPN(Reverse Polish notation), đ c phát ” ho c đ

ữ ả ậ ở ộ ỷ ế ọ ọ 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.

ự

ư

ệ

ị

GVHD: Tr nh Th Phú Sinh vê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

Ví d :ụ

ố 2. Chuyển đổi dạng Infix(trung t ) sang Postfix(h u t ậ ố )

ậ Thu t toán:

ướ ầ ủ ứ ể ể ạ ộ ọ ễ Đ c m t thành ph n c a bi u th c E (d ng Infix bi u di n B c 1:

ọ ừ ả ả ử ọ ượ ầ ằ b ng xâu, đ c t trái qua ph i). Gi s thành ph n đ c đ c là x

ướ ế ạ ế ứ ể N u x là toán h ng thì vi ả t nó vào bên ph i bi u th c E1 B c 1.1:

(xâu l uư

ả ủ ế k t qu c a Postfix)

ướ ế ẩ ấ N u x là d u ‘(’ thì đ y nó vào Stack. B c 1.2:

ướ ế ộ N u x là m t trong các phép toán +, , *, / thì B c 1.3:

ướ Xét ph n t ầ ử ở ỉ y đ nh Stack. B c 1.3.1:

ướ ế ạ ộ N u Pri(y) >= Pri(x) là m t phép toán thì lo i y ra B c 1.3.2:

ỏ ế 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

ướ ế ẩ N u Pri(y) < Pri(x) thì đ y x vào Stack. B c 1.3.3:

ướ ế ấ : N u x là d u ‘)’ thì B c 1.4

ướ ầ ử ở ầ ủ Xét ph n t đ u c a Stack. y B c 1.4.1:

ướ ỏ ế ạ y là phép toán thì lo i y ra kh i Stack, vi t y vào bên B c 1.4.2:

ở ạ ả ph i E1 và quay tr l i 1.4.1

ướ ế ạ ấ ỏ N u y là d u ‘(’ lo i y ra kh i Stack. B c 1.4.3:

ự

ư

ệ

ị

GVHD: Tr nh Th Phú Sinh vê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

ướ ậ ạ ướ ộ ể ứ ế ượ ọ L p l i b c 1 cho đ n khi toàn b bi u th c E đ c đ c qua B c 2:

ướ ạ ế ặ ạ ướ ả Lo i ph n t ầ ử ở ỉ đ nh Stack và vi t nó vào bên ph i E1. L p l i b c B c 3:

ế ỗ này cho đ n khi Stack r ng.

ướ ứ ướ ạ ậ ố ể ị ủ Tính giá tr c a bi u th c d i d ng h u t B c 4:

ứ ụ ể 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:

ướ ọ ầ ượ ầ ử ủ ứ ể ừ ế Đ 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 B c 1:

ạ ầ ử ế ặ ấ ế ẩ 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.

ướ ậ ạ ướ ế ấ ả ầ ử ứ ể 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. B c 2:

ủ ứ ỉ ị ủ lúc đó đ nh c a Stack ch a giá tr c a

ể ứ ầ bi u th c c n tính

ướ ế K t thúc. B c 3:

ự

ư

ệ

ị

GVHD: Tr nh Th Phú Sinh vê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 thu t đ c trình bày nh sau:

ố 4. Chuyển đổi dạng Infix(trung t ) sang P refix(ti nề t )ố

ậ Thu t toán :

ử ụ Stack và Queue và Stackkq. Ý t nưở : S d ng

ướ ầ ủ ứ ể ể ễ ằ ạ ộ ọ Đ 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, B c 1:

ả ử ọ ượ ầ ọ ừ ả đ c t ph i qua trái). Gi s thành ph n đ c đ c là x:

ướ ư ế ạ N u x là toán h ng thì đ a nó vào Queue. B c 1.1:

ướ ế ấ ẩ N u x là d u ‘)’ thì đ y nó vào Stack. B c 1.2:

ướ ế ộ N u x là m t trong các phép toán +, , *, / thì: B c 1.3:

ướ ế ỗ ể ỗ Ki m tra xem stack có r ng không? N u r ng, B c 1.3.1:

ế ỗ ướ ẩ đ y vào Stack, n u không r ng, sang b c 1.3.2.

ướ ấ L y ph n t ầ ử ở ỉ y đ nh Stack. B c 1.3.2:

ướ ư ấ ả ầ ử ế N u Pre(y)>=Pre(x), đ a t t c các ph n t trong B c 1.3.3:

ư ư Queue vào Stackkq, đ a y vào Stackkq, đ a x vào Stack.

ướ ế ẩ N u Pre(y)

ự

ư

ệ

ị

GVHD: Tr nh Th Phú Sinh vên th c hi n: Hoàng Năng H ng

7 ữ ệ

ể

ậ

ả

ấ Bài ti u lu n môn: C u trúc d li u và gi

ậ i thu t

ướ ế ấ N u x là d u ‘(’ thì: B c 1.4:

ướ ư ấ ả ầ ử Đ a t t c các ph n t trong Queue vào Stackkq, B c 1.4.1:

ướ ầ ử ở ầ ủ Xét ph n t đ u c a Stack. y B c 1.4.2:

ướ ư ạ ỏ y là phép toán thì lo i y ra kh i Stack, đ a y vào B c 1.4.3:

ề ướ Stackkq, quay v b c 1.4.2.

ế ạ ấ ỏ Stack. B c ướ 1.4.3: N u y là d u ‘)’ lo i y ra kh i

ướ ậ ạ ướ ộ ể ứ ế ượ ệ L p l i b c 1 cho đ n khi toàn b bi u th c E đ c duy t. B c 2:

ướ ư ấ ả ầ ử ấ ả ầ ử Đ a t t c các ph n t trong Queue vào Stackkq, t t c ph n t trong B c 3:

Stack và Stackkq.

ướ ấ ừ ầ ử ả ạ ế L y t ng ph n t trong Stackkq ra, đó là k t qu d ng Prefix. B c 4:

ướ ứ ướ ạ ể ị ủ Tính giá tr c a bi u th c d i d ng ti n t ề ố . B c 5:

ề ạ ứ ụ ể ể Ví d : Cho bi u th c sau hãy chuy n v d ng Prefix:

E = a * b + c / d

ả ậ ượ ư Gi i thu t đ c trình bày nh sau:

ứ ạ ị ể ề ố 5. Tình giá tr bi u th c d ng Prefix(ti n t )

ậ Thu t toán :

ướ ọ ầ ượ ầ ử ủ ứ ể ừ ả Đ c l n l t các ph n t c a bi u th c E1 (t ph i qua trái) B c 1:

ự

ư

ệ

ị

GVHD: Tr nh Th Phú Sinh vên th c hi n: Hoàng Năng H ng

8 ữ ệ

ể

ậ

ả

ấ Bài ti u lu n môn: C u trúc d li u và gi

ậ i thu t

ế ạ ẩ ặ Stack. B c ướ 1.1: N u g p toán h ng thì đ y nó vào

ướ ầ ử ế ấ ặ N u g p phép toán thì l y hai ph n t ế liên ti p trong B c 1.2:

ả ượ ẩ ự ế ệ Stack th c hi n phép toán, k t qu đ c đ y vào trong Stack.

ướ ậ ạ ướ ế ấ ả ầ ử ứ 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. B c 2:

ứ ầ ị ủ ủ ứ ể ỉ Lúc đó đ nh c a Stack ch a giá tr c a bi u th c c n tính.

ướ ế K t thúc. B c 3:

ụ ứ ể ị ủ Ví d : tính giá tr c a bi u th c sau: /+7 8 + 6 * + 3 2 + 5 4

ả ậ ượ ư Gi thu t đ c trình bày nh sau:

ươ

ầ ủ

IV. Ch

ng trình đ y đ

#include

ự

ư

ệ

ị

GVHD: Tr nh Th Phú Sinh vên th c hi n: Hoàng Năng H ng

9 ữ ệ

ể

ậ

ả

ấ Bài ti u lu n môn: C u trúc d li u và gi

ậ i thu t

#define OPERAND 0

#define OPERATOR 1

#define PARENT_OPEN 2

#define PARENT_CLOSE 3

#define ERROR 1000000

typedef struct _Item{

float value;

int type;

} Item;

// stack

typedef struct _STACKNODE{

Item item;

struct _STACKNODE *next;

} STACKNODE;

typedef struct _STACK{

STACKNODE *top;

int size;

} STACK;

void InitStack(STACK *stack){

ư

ự

ệ

ị

GVHD: Tr nh Th Phú Sinh vên th c hi n: Hoàng Năng H ng

10 ữ ệ

ể

ậ

ả

ấ Bài ti u lu n môn: C u trúc d li u và gi

ậ i thu t

stack >top = NULL;

stack >size = 0;

}

int IsStackEmpty(STACK *stack){

return (stack >size == 0);

}

void PushStack(STACK *stack, Item item){

if(stack >top == NULL){

stack >top = (STACKNODE

*)malloc(sizeof(STACKNODE));

stack >top >item = item;

stack >top >next = NULL;

}

else{

STACKNODE *t = (STACKNODE

*)malloc(sizeof(STACKNODE));

t >item = item;

t >next = stack >top;

stack >top = t;

}

ư

ự

ệ

ị

GVHD: Tr nh Th Phú Sinh vên th c hi n: Hoàng Năng H ng

11 ữ ệ

ể

ậ

ả

ấ Bài ti u lu n môn: C u trúc d li u và gi

ậ i thu t

stack >size++;

}

Item PopStack(STACK *stack){

if(stack >size > 0){

STACKNODE *t = stack >top;

stack >top = stack >top >next;

Item item = t >item;

free(t);

stack >size;

return item;

}

Item PeekStack(STACK *stack){

if(stack >size > 0)

return stack >top >item;

}

// queue

typedef struct _QUEUENODE{

Item item;

struct _QUEUENODE *next;

ư

ự

ệ

ị

GVHD: Tr nh Th Phú Sinh vên th c hi n: Hoàng Năng H ng

12 ữ ệ

ể

ậ

ả

ấ Bài ti u lu n môn: C u trúc d li u và gi

ậ i thu t

struct _QUEUENODE *prev;

} QUEUENODE;

typedef struct _QUEUE{

_QUEUENODE *front, *rear;

int size;

} QUEUE;

void InitQueue(QUEUE *queue){

queue >front = NULL;

queue >rear = NULL;

queue >size = 0;

}

int IsQueueEmpty(QUEUE *queue){

return (queue >size == 0);

}

void PushQueue(QUEUE *queue, Item item){

if(queue >front == NULL && queue >rear == NULL){

queue >front = (QUEUENODE

*)malloc(sizeof(QUEUENODE));

queue >front >item = item;

queue >front >next = NULL;

ư

ự

ệ

ị

GVHD: Tr nh Th Phú Sinh vên th c hi n: Hoàng Năng H ng

13 ữ ệ

ể

ậ

ả

ấ Bài ti u lu n môn: C u trúc d li u và gi

ậ i thu t

queue >front >prev = NULL;

queue >rear = queue >front;

}

else{

QUEUENODE *t = (QUEUENODE

*)malloc(sizeof(QUEUENODE));

t >item = item;

t >next = queue >front;

t >prev = NULL;

queue >front >prev = t;

queue >front = t;

}

queue>size++;

}

Item PopQueue(QUEUE *queue){

if(queue >size != 0){

QUEUENODE *t = queue>rear;

if(queue >rear == queue>front){

queue >rear = NULL;

queue >front = NULL;

ự

ư

ệ

ị

GVHD: Tr nh Th Phú Sinh vên th c hi n: Hoàng Năng H ng

14 ữ ệ

ể

ậ

ả

ấ Bài ti u lu n môn: C u trúc d li u và gi

ậ i thu t

}

else{

queue >rear = queue >rear >prev;

queue >rear >next = NULL;

}

queue >size;

Item i = t >item;

free(t);

return i;

}

Item PeekQueue(QUEUE *queue)

{

if(queue>size > 0)

return queue>front>item;

}

int DocSo(char str[], int &i){

int len = strlen(str);

int j = 0;

char t[20];

ự

ư

ệ

ị

GVHD: Tr nh Th Phú Sinh vên th c hi n: Hoàng Năng H ng

15 ữ ệ

ể

ậ

ả

ấ Bài ti u lu n môn: C u trúc d li u và gi

ậ i thu t

while(i < len){

if(str[i] >= '0' && str[i] <= '9'){

t[j++] = str[i];

}

else{

t[j++] = '\0';

break;

}

i++;

}

return atoi(t);

}

void Tach(char str[], QUEUE *queue){

int len = strlen(str);

int i = 0;

Item item;

while(i < len){

if(str[i] == '+' || str[i] == '' || str[i] == '*' || str[i] == '/'){

item.value = str[i];

item.type = OPERATOR;

ự

ư

ệ

ị

GVHD: Tr nh Th Phú Sinh vên th c hi n: Hoàng Năng H ng

16 ữ ệ

ể

ậ

ả

ấ Bài ti u lu n môn: C u trúc d li u và gi

ậ i thu t

PushQueue(queue, item);

}

else if(str[i] == '('){

item.value = str[i];

item.type = PARENT_OPEN;

PushQueue(queue, item);

}

else if(str[i] == ')'){

item.value = str[i];

item.type = PARENT_CLOSE;

PushQueue(queue, item);

}

else if(str[i] >= '0' && str[i] <= '9'){

item.value = DocSo(str, i);

item.type = OPERAND;

PushQueue(queue, item);

}

i++;

}

ự

ư

ệ

ị

GVHD: Tr nh Th Phú Sinh vên th c hi n: Hoàng Năng H ng

17 ữ ệ

ể

ậ

ả

ấ Bài ti u lu n môn: C u trúc d li u và gi

ậ i thu t

}

// do uu tien

int priority(int optr){

if(optr == '(' || optr == ')')

return 1;

if(optr == '+' || optr == '')

return 2;

if(optr == '*' || optr == '/')

return 3;

return 0;

}

// chuyen tu bieu thuc trung to sang hau to

void Convert(QUEUE *queue, QUEUE *output){

int size = queue >size;

QUEUENODE *i;

Item item;

STACK stack;

InitStack(&stack);

for(i = queue >rear; i != NULL; i = i >prev){

item = i >item;

ự

ư

ệ

ị

GVHD: Tr nh Th Phú Sinh vên th c hi n: Hoàng Năng H ng

18 ữ ệ

ể

ậ

ả

ấ Bài ti u lu n môn: C u trúc d li u và gi

ậ i thu t

switch(item.type){

case OPERAND:{

PushQueue(output, item);

}

break;

case OPERATOR:{

while(priority(item.value) <=

priority(PeekStack(&stack).value) && stack.size > 0){

Item iTemp = PopStack(&stack);

PushQueue(output, iTemp);

}

PushStack(&stack, item);

}

break;

case PARENT_OPEN:{

PushStack(&stack, item);

}

break;

case PARENT_CLOSE:{

item = PopStack(&stack);

ự

ư

ệ

ị

GVHD: Tr nh Th Phú Sinh vên th c hi n: Hoàng Năng H ng

19 ữ ệ

ể

ậ

ả

ấ Bài ti u lu n môn: C u trúc d li u và gi

ậ i thu t

while(item.type != PARENT_OPEN){

PushQueue(output, item);

item = PopStack(&stack);

}

break;

}

while(stack.size > 0) {

item = PopStack(&stack);

PushQueue(output, item);

}

void Print(QUEUE *queue){

QUEUENODE *i;

Item item;

for(i = queue >rear; i != NULL; i = i >prev){

item = i >item;

switch(item.type){

case OPERAND:

ư

ự

ệ

ị

GVHD: Tr nh Th Phú Sinh vên th c hi n: Hoàng Năng H ng

20 ữ ệ

ể

ậ

ả

ấ Bài ti u lu n môn: C u trúc d li u và gi

ậ i thu t

printf("%d ", (int)item.value);

break;

case OPERATOR:

case PARENT_OPEN:

case PARENT_CLOSE:

printf("%c ", (int)item.value);

break;

}

printf("\n");

}

// tinh gia tri cua bieu thuc hau to

float Calculate(QUEUE *queue){

float result = 0;

STACK stack;

InitStack(&stack);

QUEUENODE *i;

Item item;

for(i = queue >rear; i != NULL; i = i >prev){

item = i >item;

ư

ự

ệ

ị

GVHD: Tr nh Th Phú Sinh vên th c hi n: Hoàng Năng H ng

21 ữ ệ

ể

ậ

ả

ấ Bài ti u lu n môn: C u trúc d li u và gi

ậ i thu t

if(item.type == OPERAND)

PushStack(&stack, item);

else{ //OPERATOR

if(stack.size < 2)

return ERROR;

float a = PopStack(&stack).value;

float b = PopStack(&stack).value;

switch((int)item.value){

case '+':

result = a + b;

break;

case '':

result = b a;

break;

case '*':

result = a * b;

break;

case '/':

if(a == 0)

result = 0;

ư

ự

ệ

ị

GVHD: Tr nh Th Phú Sinh vên th c hi n: Hoàng Năng H ng

22 ữ ệ

ể

ậ

ả

ấ Bài ti u lu n môn: C u trúc d li u và gi

ậ i thu t

else

result = b / a;

}

item.value = result;

item.type = OPERAND;

PushStack(&stack, item);

}

return PopStack(&stack).value;

}

// chuyen bieu thuc trung to sang tien to

void Convert2(QUEUE *queue, QUEUE *output){

int size = queue >size;

QUEUENODE *i;

Item item;

STACK stack;

InitStack(&stack);

for(i = queue >front; i != NULL; i = i >next){

item = i >item;

switch(item.type){

ự

ư

ệ

ị

GVHD: Tr nh Th Phú Sinh vên th c hi n: Hoàng Năng H ng

23 ữ ệ

ể

ậ

ả

ấ Bài ti u lu n môn: C u trúc d li u và gi

ậ i thu t

case OPERAND:{

PushQueue(output, item);

}

break;

case OPERATOR:{

while(priority(item.value) <

priority(PeekStack(&stack).value) && stack.size > 0){

Item iTemp = PopStack(&stack);

PushQueue(output, iTemp);

}

PushStack(&stack, item);

}

break;

case PARENT_OPEN:{

item = PopStack(&stack);

while(item.type != PARENT_CLOSE){

PushQueue(output, item);

item = PopStack(&stack);

}

ư

ự

ệ

ị

GVHD: Tr nh Th Phú Sinh vên th c hi n: Hoàng Năng H ng

24 ữ ệ

ể

ậ

ả

ấ Bài ti u lu n môn: C u trúc d li u và gi

ậ i thu t

break;

case PARENT_CLOSE:{

PushStack(&stack, item);

}

break;

}

while(stack.size > 0){

item = PopStack(&stack);

PushQueue(output, item);

}

void Print2(QUEUE *queue){

QUEUENODE *i;

Item item;

for(i = queue >front; i != NULL; i = i >next){

item = i >item;

switch(item.type){

case OPERAND:

printf("%d ", (int)item.value);

ư

ự

ệ

ị

GVHD: Tr nh Th Phú Sinh vên th c hi n: Hoàng Năng H ng

25 ữ ệ

ể

ậ

ả

ấ Bài ti u lu n môn: C u trúc d li u và gi

ậ i thu t

break;

case OPERATOR:

case PARENT_OPEN:

case PARENT_CLOSE:

printf("%c ", (int)item.value);

break;

}

printf("\n");

}

// tinh gia tri cua bieu thuc tien to

float Calculate2(QUEUE *queue){

float result = 0;

STACK stack;

InitStack(&stack);

QUEUENODE *i;

Item item;

for(i = queue >rear; i != NULL; i = i >prev){

item = i >item;

if(item.type == OPERAND)

ự

ư

ệ

ị

GVHD: Tr nh Th Phú Sinh vên th c hi n: Hoàng Năng H ng

26 ữ ệ

ể

ậ

ả

ấ Bài ti u lu n môn: C u trúc d li u và gi

ậ i thu t

PushStack(&stack, item);

else{ //OPERATOR

if(stack.size < 2)

return ERROR;

float a = PopStack(&stack).value;

float b = PopStack(&stack).value;

switch((int)item.value){

case '+':

result = a + b;

break;

case '':

result = a b;

break;

case '*':

result = a * b;

break;

case '/':

if(b == 0)

result = 0;

else

ự

ư

ệ

ị

GVHD: Tr nh Th Phú Sinh vên th c hi n: Hoàng Năng H ng

27 ữ ệ

ể

ậ

ả

ấ Bài ti u lu n môn: C u trúc d li u và gi

ậ i thu t

result = a / b;

}

item.value = result;

item.type = OPERAND;

PushStack(&stack, item);

}

return PopStack(&stack).value;

}

int main()

{

char str[100];

float t;

QUEUE infix, postfix, prefix;

InitQueue(&infix);

InitQueue(&postfix);

InitQueue(&prefix);

printf("\nNhap bieu thuc trung to: ");

gets(str);

Tach(str, &infix);

ự

ư

ệ

ị

GVHD: Tr nh Th Phú Sinh vên th c hi n: Hoàng Năng H ng

28 ữ ệ

ể

ậ

ả

ấ Bài ti u lu n môn: C u trúc d li u và gi

ậ i thu t

Convert(&infix, &postfix);

printf("\nBieu thuc hau to la: ");

Print(&postfix);

t = Calculate(&postfix);

if(t == ERROR)

printf("\nBieu thuc loi!");

else

printf("\nGia tri bieu thuc: %0.2f", t);

printf("\n");

Convert2(&infix, &prefix);

printf("\nBieu thuc tien to la: ");

Print2(&prefix);

t = Calculate2(&prefix);

if(t == ERROR)

printf("\nBieu thuc loi!");

else

printf("\nGia tri bieu thuc: %0.2f", t);

getch();

return 0;

}

ự

ư

ệ

ị

GVHD: Tr nh Th Phú Sinh vên th c hi n: Hoàng Năng H ng

29 ữ ệ

ể

ậ

ả

ấ Bài ti u lu n môn: C u trúc d li u và gi

ậ i thu t

ả ư ế K t qu nh sau:

ậ ụ ề ể ể ậ ẫ ấ v n còn r t nhi u cách khác thu t toán khác đ có th áp d ng Nh n xét:

ứ ể ố ậ ố ề ố ứ ể ể chuy n 1 bi u th c trung t sang h u t và ti n t ị ủ , tính giá tr c a bi u th c

ề ố ậ ố ế ư ầ ủ ụ ấ ti n t và h u t ấ . Th nh ng đây là cách đ y đ và rõ ràng nh t. Nó áp d ng r t

ườ ầ ủ ử ụ ậ ở ồ ố t ư t cho nh ng ng ả i đang l p trình. B i vì nó bao g m đ y đ , s d ng c

Stack và Queue.

ế

ậ

ầ

Ph n III: K t lu n

ề ứ ủ ụ ệ ể Thông qua vi c tìm hi u v ng d ng c a Stack và Queue đ ể đ vi ể ế t

ươ ứ ể ế ổ ố ề ch ng trình bi n đ i bi u th c trung t thành ti n t ị ủ , ố h u tậ ố và tính giá tr c a

ề ố ể ậ ố ượ ấ ừ ề ề ị ứ bi u th c ti n t và h u t em đã rút ra đ c r t nhi u đi u. T cách xác đ nh

ả ậ ế ư ươ ạ ượ đ c gi i thu t đ n t duy logic và ch ầ ng trình đã ch y thành công trên ph n

ữ ề ằ ượ ộ m m Devcpp++ 5.11 b ng ngôn ng C/C++. Rút ra đ ể c cách làm m t bài ti u

ậ ẩ lu n đúng và chu n.

ự

ư

ệ

ị

GVHD: Tr nh Th Phú Sinh vên th c hi n: Hoàng Năng H ng

30 ữ ệ

ể

ậ

ả

ấ Bài ti u lu n môn: C u trúc d li u và gi

ậ i thu t

ượ ế ự ạ ả ờ ỗ ị Có đ c k t qu trên là nh có s d y d chu đáo c a ủ cô giáo Tr nh Th ị

ụ ế ữ ệ ứ ấ ả ề Phú trong quá trình truy n th ki n th c môn h c ọ c u trúc d li u và gi i thu t ậ ,

ẫ ậ ự ệ ồ đ ng th ời cô cũng là ng ườ ướ i h ố ng d n t n tình trong su t quá trình th c hi n đ ề

ể ậ ọ tài ti u lu n môn h c này.

Em xin chân thành cám n côơ !

Thanh Hóa, ngày….tháng 11 năm 2015

ướ ẫ ự Giáo viên h ng d n ệ Sinh viên th c hi n

ị ị Ths. Tr nh Th Phú Hoàng Năng H ngư

Ả

Ệ

TÀI LI U THAM KH O

ữ ệ ấ ả ạ ọ ậ ỗ ố [1] Giáo trình c u trúc d li u và gi i thu t, Đ Xuân Lôi, NXB Đ i h c Qu c

Gia Hà N i.ộ

ậ ả [2] L p trình C căn b n, Hanoi Aptech Computer Education Center .

ạ Ấ ậ ậ ơ ở ỹ [3] Gs. Ph m Văn t. K thu t l p trình C c s và nâng cao, NXB Giao thông