[123doc] - cai-dat-thuat-toan-bien-doi-bieu-thuc-tu-trung-to-sang-hau-to-su-dung-cau-truc-du-lieu-stack-dang-mang

abc

Report
Giảng viên hướng dẫn:Nguyễn Thị Quỳnh Như
Sinh viên thực hiện:Nguyễn Việt Dũng
Nguyễn Văn Quỳnh
Nguyễn Văn Bình
Lớp: 1210A04
Chuyên ngành: Công nghệ thông tin
HàNội - Năm 2014
I,Phát biểu bài toán
-
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ể hiểu để thực hiện.
II, Một số định nghĩa
1. Biếu thức trung tố là gì?
-
Biểu thức trung tố là biểu thức mà toán tử sẽ được đặt giữa hai toán
hạng, dĩ nhiên đây phải là toán tử hai ngôi. Hay đơn giản nó là các phép
tính mà ta bắt gặp hàng ngày trong học tập, đời sống.
Vd:
a+b
1+2+4
2. Biểu thức hậu tố là gì?
Biểu thức hậu tố là biểu thức mà toán tử đứng sau toán hạng, và tất
nhiên đây phải là toán tử hai ngôi. Nó còn được gọi là “ký pháp
nghịch đảo Ba Lan”.
Vd: ab+
12+4+
-
III, Tìm hiểu bài toán
Chọn ngôn ngữ lập trình :ngôn ngữ C.
Cài đặt trên mảng và danh sách liên kết đơn
Input : Biểu thức trung tố
10+4-6/5*9
- Output: Biểu thức hậu tố
10 +6 5/9*1. Stack
-
-
Stack là một dạng danh sách đặc biệt trong đó cách thao tác chỉ được
thực hiện trên một đầu của Stack
-
Đầu này được gọi là đỉnh của ngăn xếp
Các phần tử vào trước sẽ được lấy ra sau, hay gọi là danh sách
LIFO(Last In First Out)
•
Cài đặt bằng mảng một chiều
a[0]
Đáy ngăn xếp
•
Đỉnh ngăn xếp
Cài đặt bằng danh sách liên kết đơn
Head
Tail
……
Đỉnh ngăn xếp
2. Thuật toán
-
1, Khởi tạo ngăn xếp rỗng
2, Đọc các phần tử trong biểu thức trung tố :
Toán hạng: hiển thị nó ra out put
Nếu phần tử là :
Dấu ‘(’ : đưa vào S
NULL
Đáy ngăn xếp
-
Dấu ‘)’ : Lấy toàn bộ toán tử trong S ra cho đến khi gặp dấu ‘(’,dấu ‘(’
cũng được đưa ra
Toán tử:
Nếu toán tử có độ ưu tiên cao hơn so với toán tử ở đỉnh S thì đưa toán
tử đó vào S.
Ngược lại lấy ra và hiển thị toán tử ở đỉnh S
Sau khi duyệt hết nếu trong S còn phần tử thì lấy lần lượt nó ra cho vào
output.
Phần cài đặt:
#include<stdio.h>
#define SIZE 50
#include <ctype.h>
char infx[50], pofx[50], ch, x;
char s[SIZE];
int top = -1;
push(char x) {
s[++top] = x;
}
char pop() {
return (s[top--]);
}
int doUuTien(char x) {
switch (x){
case '#':
return 0;
case '(':
return 1;
case '+':
case '-':
return 2;
case '*':
case '/':
return 3;
}
}
void convert(){
int i=0,k=0;
printf("\nMoi ban nhap bieu thuc trung to: ");
scanf("%s", infx);
push('#');
while ((ch = infx[i++]) != '\0') {
if (ch == '(')
push(ch);
else if (isalnum(ch))
pofx[k++] = ch;
else if (ch == ')') {
while (s[top] != '(')
pofx[k++] = pop();
x = pop();
} else {
while (doUuTien(s[top]) >= doUuTien(ch))
pofx[k++] = pop();
push(ch);
}
}
while (s[top] != '#')
pofx[k++] = pop();
pofx[k] = '\0';
printf("Bieu thuc so hau to la: %s\n", pofx);
}
main() {
char infx[50], pofx[50], ch, x;
char c = 'y';
printf("\n-------***CHUYEN TU BIEU THUC TRUNG TO SANG BIEU
THUC HAU TO***-------\n");
while(c == 'y'){
convert();
fflush(stdin);
printf("Ban co muon nhap tiep?y/n?");
scanf("%c",&c);
}
}
Chương trình khi chạy
Ví dụ:
Input: 10-3*(14-2)/12
Kí Tự
Stack
10
Out put
10
-
-
10
3
-
10 3
*
-*
10 3
(
-*(
10 3
14
-*(
10 3 14
-
-*(-
10 3 14
2
-*(-
10 3 14 2
)
-*
10 3 14 2 - *
/
-/
10 3 14 2 - *
12
-/
10 3 14 2 - * 12
““
Out put: 10 3 14 2 * - * 12
10 3 14 2 - * 12 / -

similar documents