Giải thuật sử dụng CTDL Ngăn Xếp (Stack) trong bài tập tính giá trị biểu thức
- Bước 1: cắt chuỗi biểu thức thành từng toán tử hoặc toán hạng
- Bước 2a: nếu không phải là dấu đóng ngoặc đơn “)” thì đưa vào stack1
- Bước 2b: nếu gặp dấu đóng ngoặc đơn “)” thì không đưa vào stack1
- Bước 2b.1: lấy từng phần tử trong stack1 ra đưa vào stack2 cho đến khi gặp dấu mở ngoặc đơn “(“.
- Bước 2b.2: tính biểu thức trong stack2.
- Bước 2b.3: đưa kết quả của biểu thức trong stack2 vào stack1.
- Bước 3: lặp lại cho đến khi hết toán tử hoặc toán hạng trong chuỗi biểu thức
- Bước 4: lấy từng phần tử trong stack1 đưa vào stack2
- Bước 5: tính biểu thức trong stack2
- Kết quả của bước 5 là kết quả của chuỗi biểu thức cần tính
Nguyễn Hoàng Phát (bài giảng môn CTDL và Giải Thuật)