Cấu trúc dữ liệu - Phân tích cú pháp biểu thức
Cách viết biểu thức số học được gọi là notation. Một biểu thức số học có thể được viết bằng ba ký hiệu khác nhau nhưng tương đương, tức là, không làm thay đổi bản chất hoặc đầu ra của một biểu thức. Các ký hiệu này là -
- Ký hiệu tiền tố
- Tiền tố (tiếng Ba Lan)
- Ký hiệu Postfix (Reverse-Polish)
Các ký hiệu này được đặt tên như cách chúng sử dụng toán tử trong biểu thức. Chúng ta sẽ tìm hiểu tương tự ở đây trong chương này.
Ký hiệu tiền tố
Chúng tôi viết biểu thức trong infix ký hiệu, ví dụ a - b + c, trong đó các toán tử được sử dụng in-giữa các toán hạng. Con người chúng ta có thể dễ dàng đọc, viết và nói bằng ký hiệu infix nhưng điều này cũng không hiệu quả với các thiết bị máy tính. Một thuật toán để xử lý ký hiệu infix có thể khó khăn và tốn kém về thời gian và không gian tiêu thụ.
Ký hiệu tiền tố
Trong ký hiệu này, toán tử là prefixed thành toán hạng, tức là toán tử được viết trước toán hạng. Ví dụ,+ab. Điều này tương đương với ký hiệu infix của nóa + b. Ký hiệu tiền tố còn được gọi làPolish Notation.
Ký hiệu Postfix
Kiểu ký hiệu này được gọi là Reversed Polish Notation. Trong kiểu ký hiệu này, toán tử làpostfixed cho toán hạng tức là toán tử được viết sau toán hạng. Ví dụ,ab+. Điều này tương đương với ký hiệu infix của nóa + b.
Bảng sau đây cố gắng chỉ ra ngắn gọn sự khác biệt trong cả ba ký hiệu:
| Sr.No. | Ký hiệu tiền tố | Ký hiệu tiền tố | Ký hiệu Postfix |
|---|---|---|---|
| 1 | a + b | + ab | ab + |
| 2 | (a + b) ∗ c | ∗ + abc | ab + c ∗ |
| 3 | a ∗ (b + c) | ∗ a + bc | abc + ∗ |
| 4 | a / b + c / d | + / ab / cd | ab / cd / + |
| 5 | (a + b) ∗ (c + d) | ∗ + ab + cd | ab + cd + ∗ |
| 6 | ((a + b) ∗ c) - d | - ∗ + abcd | ab + c ∗ d - |
Phân tích cú pháp biểu thức
Như chúng ta đã thảo luận, đây không phải là cách hiệu quả để thiết kế một thuật toán hoặc chương trình để phân tích cú pháp các ký hiệu infix. Thay vào đó, các ký hiệu tiền tố này trước tiên được chuyển đổi thành ký hiệu hậu tố hoặc tiền tố và sau đó được tính toán.
Để phân tích cú pháp bất kỳ biểu thức số học nào, chúng ta cũng cần quan tâm đến mức độ ưu tiên của toán tử và tính kết hợp.
Quyền ưu tiên
Khi một toán hạng nằm giữa hai toán tử khác nhau, toán tử nào sẽ lấy toán hạng trước, được quyết định bởi sự ưu tiên của một toán tử so với những toán tử khác. Ví dụ -
Vì phép toán nhân được ưu tiên hơn phép cộng nên b * c sẽ được đánh giá trước. Bảng ưu tiên toán tử được cung cấp sau.
Sự liên kết
Tính liên kết mô tả quy tắc trong đó các toán tử có cùng mức độ ưu tiên xuất hiện trong một biểu thức. Ví dụ, trong biểu thức a + b - c, cả + và - đều có cùng mức độ ưu tiên, thì phần nào của biểu thức sẽ được đánh giá trước, được xác định bởi tính kết hợp của các toán tử đó. Ở đây, cả + và - đều có liên quan trái, vì vậy biểu thức sẽ được đánh giá là(a + b) − c.
Mức độ ưu tiên và tính liên kết xác định thứ tự đánh giá một biểu thức. Sau đây là bảng liên kết và ưu tiên toán tử (cao nhất đến thấp nhất):
| Sr.No. | Nhà điều hành | Quyền ưu tiên | Sự liên kết |
|---|---|---|---|
| 1 | Luỹ thừa ^ | Cao nhất | Liên kết phù hợp |
| 2 | Phép nhân (∗) & Phép chia (/) | Cao thứ hai | Liên kết trái |
| 3 | Phép cộng (+) & Phép trừ (-) | Thấp nhất | Liên kết trái |
Bảng trên cho thấy hành vi mặc định của các toán tử. Tại bất kỳ thời điểm nào trong đánh giá biểu thức, thứ tự có thể được thay đổi bằng cách sử dụng dấu ngoặc đơn. Ví dụ -
Trong a + b*c, phần biểu hiện b*csẽ được đánh giá đầu tiên, với phép nhân được ưu tiên hơn phép cộng. Ở đây chúng tôi sử dụng dấu ngoặc đơn choa + b được đánh giá đầu tiên, như (a + b)*c.
Thuật toán đánh giá Postfix
Bây giờ chúng ta sẽ xem xét thuật toán về cách đánh giá ký hiệu hậu tố -
Step 1 − scan the expression from left to right
Step 2 − if it is an operand push it to stack
Step 3 − if it is an operator pull operand from stack and perform operation
Step 4 − store the output of step 3, back to stack
Step 5 − scan the expression until all operands are consumed
Step 6 − pop the stack and perform operationĐể xem cách triển khai bằng ngôn ngữ lập trình C, vui lòng nhấp vào đây .