Chương 2 Xử lí dãy lệnh và biểu thức
2.1 Val
Cho 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;
}
}
Chia sẻ với bạn bè của bạn: |