TỦ SÁch tri thức duy tân nguyễn xuân huy sáng tạo trong thuật toán và LẬp trìNH
Chương 2 Xử lí dãy lệnh và biểu thức
tải về 2.51 Mb.
|
- Điều hướng trang này:
- Độ phức tạp.
Chương 2 Xử lí dãy lệnh và biểu thức2.1 ValCho các biến được gán trị a = 0, b = 1, c = 2,..., z = 25. Tính trị của biểu thức số học được viết đúng cú pháp, chứa các tên biến, các phép toán +, –, *, và / (chia nguyên) và các cặp ngoặc (). Thí dụ, biểu thức, (b+c)*(e–b) + (y–x) sẽ có giá trị (1+2)*(4–1)+ (24–23) = 3*3+1 = 10. Thuật toán Do phải ưu tiên thực hiện các phép toán nhân (*) và chia (/) trước các phép toán cộng (+) và trừ (), ta qui ước các phép toán nhân và chia có bậc cao hơn bậc của các phép toán cộng và trừ. Gọi s là string chứa biểu thức, ta duyệt lần lượt từng kí tự s[i] của s và sử dụng hai ngăn xếp v và c để xử lí các tình huống sau: 1. Nếu s[i] là biến 'a', 'b',… thì ta nạp trị tương ứng của biến đó vào ngăn xếp (stack) v. 2. Nếu s[i] là dấu mở ngoặc '(' thì ta nạp dấu đó vào ngăn xếp c. 3. Nếu s[i] là các phép toán '+', '–', '*', '/' thì ta so sánh bậc của các phép toán này với bậc của phép toán p trên ngọn ngăn xếp c. 3.1. Nếu Bac(s[i]) Bac(p) thì ta lấy phép toán p ra khỏi ngăn xếp c và thực hiện phép toán đó với 2 phần tử trên cùng của ngăn xếp v. Bước này được lặp đến khi Bac(s[i]) > Bac(p). Sau đó làm tiếp bước 3.2. 3.2 Nạp phép toán s[i] vào ngăn xếp c. 4. Nếu s[i] là dấu đóng ngoặc ')' thì ta dỡ dần và thực hiện các phép toán trên ngọn ngăn xếp c cho đến khi gặp dấu '(' đã nạp trước đó. Thuật toán được xây dựng trên giả thiết biểu thức s được viết đúng cú pháp. Về bản chất, thuật toán xử lý và tính toán đồng thời trị của biểu thức s theo nguyên tắc phép toán sau hay là kí pháp Ba Lan do nhà toán học Ba Lan Lucasievics đề xuất. Theo kí pháp này, biểu thức (b+c)*(e–b) + (y–x) sẽ được viết thành bc+eb–*yx–+ và được thực hiện trên ngăn xếp v như sau. Gọi iv là con trỏ ngọn của ngăn xếp v, iv được khởi trị 0: 1. Nạp trị của biến b vào ngăn xếp v: iv := iv + 1; v[iv] := (b); trong đó (b) là trị của biến b. 2. Nạp trị của biến c vào ngăn xếp v: iv := iv + 1; v[iv] := (c); 3. Thực hiện phép cộng hai phần tử trên ngọn ngăn xếp v, ghi kết quả vào ngăn dưới, bỏ ngăn trên: v[iv–1] := v[iv–1] + v[iv]; iv := iv –1; 4. Nạp trị của e vào ngăn xếp v: iv := iv + 1; v[iv] := (e); 5. Nạp trị của b vào ngăn xếp v: iv := iv + 1; v[iv] := (b); 6. Thực hiện phép trừ hai phần tử trên ngọn ngăn xếp v, ghi kết quả vào ngăn dưới, bỏ ngăn trên: v[iv–1] := v[iv–1] – v[iv]; iv := iv –1; 7. Thực hiện phép nhân hai phần tử trên ngọn ngăn xếp v, ghi kết quả vào ngăn dưới, bỏ ngăn trên: v[iv–1] := v[iv–1] * v[iv]; iv := iv –1; 8. Nạp trị của y vào ngăn xếp v: iv := iv + 1; v[iv] := (y); 9. Nạp trị của x vào ngăn xếp v: iv := iv + 1; v[iv] := (x); 10. Thực hiện phép trừ hai phần tử trên ngọn ngăn xếp v, ghi kết quả vào ngăn dưới, bỏ ngăn trên: v[iv–1] := v[iv–1] – v[iv]; iv := iv –1; 11. Thực hiện phép cộng hai phần tử trên ngọn ngăn xếp v, ghi kết quả vào ngăn dưới, bỏ ngăn trên: v[iv–1] := v[iv–1] + v[iv]; iv := iv –1; Kết quả cuối cùng có trong v[iv]. Bạn nhớ khởi trị ngăn xếp c bằng kí tự nào đó không có trong biểu thức, thí dụ '#'. Phép toán này sẽ có bậc 0 và dùng làm phần tử đệm để xử lý tình huống 3. Bạn cần đặt kí hiệu # vào đáy của ngăn xếp c để làm lính canh. Vì khi quyết định có nạp phép toán p nào đó vào ngăn xếp c ta cần so sánh bậc của p với bậc của phép toán trên ngọn của ngăn xếp c. Như vậy # sẽ có bậc 0. Bạn có thể thêm một phép kiểm tra để phát hiện lỗi "chia cho 0" khi thực hiện phép chia. Bạn cũng có thể phát triển thêm chương trình để có thể xử lí các biểu thức có chứa các phép toán một ngôi !, ++, – –. ... và các lời gọi hàm. Độ phức tạp. cỡ n, trong đó n là số kí hiệu trong biểu thức.(* Val.pas *) uses crt; const fn = 'val.inp'; gn = 'val.out'; nl = #13#10; bl = #32; mn = 500; var c: array[0..mn] of char; {Ngăn xếp c chứa các phép toán} ic: integer; v: array[0..mn] of integer; {Ngăn xếp v chứa trị của các biến} iv: integer; function LaBien(c: char): Boolean; begin LaBien := (c in ['a'..'z']); end; function LaPhepToan(c: char): Boolean; begin LaPhepToan := (c in ['+','-','*','/']) end; function Val(c: char): integer; { trị của biến c } begin Val := Ord(c)-ord('a'); end; function Bac(p: char): integer; { Bậc của phép toán p } begin if (p in ['+','-']) then Bac := 1 else if (p in ['*','/']) then Bac := 2 else Bac := 0; end; (* Thực hiện phép toán 2 ngôi trên ngọn ngăn xếp v *) procedure Tinh(p: char); begin case p of '+': begin v[iv-1] := v[iv-1] + v[iv]; dec(iv) end; '-': begin v[iv-1] := v[iv-1] - v[iv]; dec(iv) end; '*': begin v[iv-1] := v[iv-1] * v[iv]; dec(iv) end; '/': begin v[iv-1] := v[iv-1] div v[iv]; dec(iv) end; end end; procedure XuLiToan(p: char); begin while (Bac(c[ic]) >= Bac(p)) do begin Tinh(c[ic]); dec(ic) end; inc(ic); c[ic] := p; { nap phep toan p } end; procedure XuLiNgoac; begin while (c[ic] <> '(') do begin Tinh(c[ic]); dec(ic) end; dec(ic); { Bo ngoac } end; function XuLi(s: string): integer; var i: integer; begin ic := 0; c[ic] := '#'; iv := -1; for i := 1 to length(s) do if LaBien(s[i]) then begin inc(iv); v[iv] := Val(s[i]) end else if s[i] = '(' then begin inc(ic); c[ic] := '(' end else if LaPhepToan(s[i]) then XuLiToan(s[i]) else if s[i] = ')' then XuLiNgoac; while (ic > 0) do begin Tinh(c[ic]); dec(ic) end; XuLi := v[iv]; end; BEGIN writeln(nl,XuLi('(b+c)*(f-a+b-c+d)/(c*d+b)')); { 3 } readln; END. // DevC++: Val #include #include #include #include using namespace std; // Mo ta Dư lieu va bien const int mn = 500; char s[mn]; // bieu thuc char c[mn]; //ngan xep phep toan va dau ( int ic; // con trỏ ngăn xếp c int v[mn]; //ngan xep tinh toan int iv; // con trỏ ngăn xếp v int kq; // ket qua int n; // len – số ki tự trong biểu thức // Khai báo các hàm int XuLi(); bool LaBien(char c); // kiem tra c la bien ? bool LaPhepToan(char c); // kiem tra c la phep toan +, –, *, / ? void XuLiPhepToan(char pt); void XuLiNgoac(); int Bac(char pt); // Bac cua phep toan +, – (1), *, / (2) int Val(char c); // Tinh tri cua bien c void Tinh(char pt); // thuc hien phep toan pt // Cai dat int main() { strcpy(s,"(b+c)*(e-b) + (y-x)"); cout << endl << " input: " << s; kq = XuLi(); cout << endl << endl << " Dap so: " << kq << endl ; cout << endl << endl << " Fini" << endl; cin.get(); return 0; } int XuLi() { ic = 0; c[ic] = '#'; n = strlen(s); iv = -1; int i; for (i = 0; i < n; ++i) if (LaBien(s[i])) v[++iv] = Val(s[i]); else if (s[i]=='(') c[++ic] = '('; else if (s[i]==')') XuLiNgoac(); else if (LaPhepToan(s[i])) XuLiPhepToan(s[i]); while (LaPhepToan(c[ic])) { Tinh(c[ic]); --ic; } return v[iv]; } // Val('A') = 0; Val('B') = 1; . . . int Val(char c) { return (int)(c-'a'); } int Bac(char pt) { if (pt == '+' || pt == '-') return 1; else if (pt == '*' || pt == '/') return 2; else return 0; } bool LaBien(char c) { return (c >= 'a' && c <= 'z'); } bool LaPhepToan(char c) {return(c=='+'||c=='-'||c=='*'||c=='/');} void XuLiPhepToan(char pt) { while (Bac(c[ic]) >= Bac(pt)) { Tinh(c[ic]); --ic; } c[++ic] = pt; } void XuLiNgoac(){ while (c[ic] != '(') { Tinh(c[ic]); --ic; } --ic; // bo dau '(' } void Tinh(char pt) { // Thuc hien phép toan pt switch(pt) { case '+': v[iv-1] = v[iv-1]+v[iv]; --iv; break; case '-': v[iv-1] = v[iv-1]-v[iv]; --iv; break; case '*': v[iv-1] = v[iv-1]*v[iv]; --iv; break; case '/': v[iv-1] = v[iv-1]/v[iv]; --iv; break; } } Каталог: tailieu tailieu -> MỘt số thủ thuật khi sử DỤng phần mềm adobe presenter tạo bài giảng e-learning tailieu -> Trung tâM ĐÀo tạo mạng máy tính nhất nghệ 105 Bà Huyện Thanh Quan – 205 Võ Thị Sáu, Q3, tp. Hcm tailieu -> Céng hßa x· héi chñ nghÜa viÖt nam Độc lập tự do hạnh phúc tailieu -> Lê Xuân Biểu giao thông vận tảI ĐẮk lắK 110 NĂm xây dựng và phát triểN (1904 2014) nhà xuất bảN giao thông vận tảI tailieu -> ĐỀ thi học sinh giỏi tỉnh hải dưƠng môn Toán lớp 9 (2003 2004) (Thời gian : 150 phút) Bài 1 tailieu -> A. ĐẠi số TỔ HỢp I. Kiến thức cơ bản quy tắc cộng tailieu -> Wikipedia luôn có mặt mỗi khi bạn cần giờ đây Wikipedia cần bạn giúp tailieu -> CHÍnh phủ CỘng hòa xã HỘi chủ nghĩa việt nam độc lập Tự do Hạnh phúc tailieu -> VĂn phòng cộng hoà XÃ HỘi chủ nghĩa việt nam tải về 2.51 Mb. Chia sẻ với bạn bè của bạn:
|