tailieunhanh - Sáng tạo trong thuật toán và lập trình với ngôn ngữ Pascal và C# Tập 3 - Chương 2

Xử lí dãy lệnh và biểu thức 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. | Chương 2 Xử lí dãy lệnh và biểu thức 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. . 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 . 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