Phân tích biểu thức
Cách viết biểu thức số học được gọi là ký hiệu . 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, nghĩa là không thay đổi bản chất hoặc đầu ra của một biểu thức. Những ký hiệu này là:
- Ký hiệu Infix
- Ký hiệu Prefix (Polish)
- Ký hiệu Postfix (Reverse-Polish)
Các ký hiệu này được đặt tên là cách chúng sử dụng toán tử trong biểu thức. Chúng ta sẽ học tương tự ở đây trong chương này.
Ký hiệu Infix
Chúng ta viết biểu thức trong ký hiệu infix , ví dụ a - b + c, trong đó các toán tử được sử dụng ở giữa các toán hạng. Con người chúng ta dễ dàng đọc, viết và nói theo ký hiệu infix nhưng điều tương tự không phù hợp 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à bộ nhớ tiêu thụ.
Ký hiệu Prefix
Trong ký hiệu này, toán tử là prefixed cho 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
Phong cách 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 thể hiện sự khác biệt trong cả ba ký hiệu
Phân tích cú pháp
Như chúng ta đã thảo luận, nó không phải là một cách rất hiệu quả để thiết kế một thuật toán hoặc chương trình để phân tích các ký hiệu infix. Thay vào đó, các ký hiệu infix này trước tiên được chuyển đổi thành ký hiệu postfix hoặc prefix và sau đó được tính toán.
Để phân tích bất kỳ biểu thức số học nào, chúng ta cũng cần phải quan tâm đến quyền ư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 ở 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 toán tử so với các toán tử khác. Ví dụ:
Vì phép nhân được ưu tiên hơn phép cộng, b * c sẽ được đánh giá trước. Một bảng ưu tiên toán tử được cung cấp sau.
Kết hợp
Associativity 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à - có cùng mức ưu tiên, sau đó 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à - là liên kết trái, vì vậy biểu thức sẽ được đánh giá là (a + b) - c .
Ưu tiên và kết hợp xác định thứ tự đánh giá của một biểu thức. Sau đây là bảng ưu tiên toán tử và bảng kết hợp (cao nhất đến thấp nhất)
Bảng trên cho thấy hành vi mặc định của các nhà khai thác. 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 thức b * c sẽ được đánh giá đầu tiên, với phép nhân là ưu tiên so với phép cộng. Ở đây chúng tôi sử dụng dấu ngoặc đơn cho a + b để được đánh giá trước, 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 postfix
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
- Hiếu Kiều -
Bài viết nổi bật
Bài viết nổi bật