Giải Thuật Và Lập Trình: §7. Ký Pháp Tiền Tố, Trung Tố Và Hậu Tố | V1Study

Trang chủ » Chuyển Biểu Thức Trung Tố Sang Hậu To C » Giải Thuật Và Lập Trình: §7. Ký Pháp Tiền Tố, Trung Tố Và Hậu Tố | V1Study

Có thể bạn quan tâm

BIỂU THỨC DƯỚI DẠNG CÂY NHỊ PHÂN

Chúng ta có thể biểu diễn các biểu thức số học gồm các phép toán cộng, trừ, nhân, chia bằng một cây nhị phân, trong đó các nút lá biểu thị các hằng hay các biến (các toán hạng), các nút không phải là lá biểu thị các toán tử (phép toán số học chẳng hạn). Mỗi phép toán trong một nút sẽ tác động lên hai biểu thức con nằm ở cây con bên trái và cây con bên phải của nút đó.

Ví dụ: Cây biểu diễn biểu thức (6 / 2 + 3) * (7 - 4) như sau:

http://v1study.com/public/images/article/giai-thuat-va-lap-trinh-bieu-thuc-duoi-dang-cay-nhi-phan.png

Biểu thức dưới dạng cây nhị phân

CÁC KÝ PHÁP CHO CÙNG MỘT BIỂU THỨC

Với cây nhị phân biểu diễn biểu thức trong hình trên thì:

  • Nếu duyệt theo thứ tự trước, ta sẽ được * + / 6 2 3 - 7 4, đây là dạng tiền tố (prefix) của biểu thức. Trong ký pháp này, toán tử được viết trước hai toán hạng tương ứng, người ta còn gọi ký pháp này là ký pháp Ba Lan.
  • Nếu duyệt theo thứ tự giữa, ta sẽ được 6 / 2 + 3 * 7 - 4. Ký pháp này hơi mập mờ vì thiếu dấu ngoặc. Nếu thêm vào thủ tục duyệt inorder việc bổ sung các cặp dấu ngoặc vào mỗi biểu thức con sẽ thu được biểu thức (((6 / 2) + 3) * (7 - 4)). Ký pháp này gọi là dạng trung tố (infix) của một biểu thức (Thực ra chỉ cần thêm các dấu ngoặc đủ để tránh sự mập mờ mà thôi, không nhất thiết phải thêm vào đầy đủ các cặp dấu ngoặc).
  • Nếu duyệt theo thứ tự sau, ta sẽ được 6 2 / 3 + 7 4 - *, đây là dạng hậu tố (postfix) của biểu thức. Trong ký pháp này toán tử được viết sau hai toán hạng, người ta còn gọi ký pháp này là ký pháp nghịch đảo Balan (Reverse Polish Notation - RPN)

Chỉ có dạng trung tố mới cần có dấu ngoặc, dạng tiền tố và hậu tố không cần phải có dấu ngoặc.

Từ khóa » Chuyển Biểu Thức Trung Tố Sang Hậu To C