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 thông tin
- Tiền tố (tiếng Ba Lan)
- Ký hiệu Postfix (đảo ngược tiếng Ba Lan)
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 thông tin
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ị điện toán. 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à tiền tố ed 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à Ký hiệu Ba Lan .
Ký hiệu hậu tố
Phong cách ký hiệu này được gọi là Ký hiệu Ba Lan đảo ngược . Trong kiểu ký hiệu này, toán tử là postfix ed 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 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ử đó. Tại đây, cả hai + và - còn lại kết hợp, vì vậy biểu thức sẽ được đánh giá như (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Được cập nhật: 14 tháng 4 lúc 0:47:52 | Lượt xem: 487
