Hướng dẫn chuyển trung tố sang hậu tố

Các biểu thức đại số được sử dụng hằng ngày đều được biểu diễn dưới dạng trung tố (infix). Cách biểu diễn này rất dễ hiểu với con người vì hầu hết các toán tử (+, -, *, /) đều là toán tử hai ngôi và chúng phân cách giữa hai toán hạng với nhau. Tuy nhiên đối với máy tính, để tính được giá trị của một biểu thức đại số theo dạng này không đơn giản như ta vẫn làm. Để khắc phục điều đó, máy tính cần chuyển cách biểu diễn các biểu thức đại số từ trung tố sang một dạng khác là tiền tố hoặc hậu tố.

Thế nào là biểu thức tiền tố, trung tố và hậu tố

Trong đoạn giới thiệu trên có lẽ bạn cũng hình dung được thế nào là biểu thức trung tố, hiểu đơn giản tức là toán tử sẽ được đặt giữa hai toán hạng, dĩ nhiên đây phải là toán tử hai ngôi. Vậy dựa vào vị trí của của toán tử, liệu ta có thể biểu diễn biểu thức đại số dưới dạng khác? Câu trả lời là được, và như đã nói, ta có ba cách là biểu thức tiền tố (prefix), trung tố (infix) và hậu tố (postfix). Hãy xem một chút giới thiệu về cách biểu diễn biểu thức tiền tố và hậu tố để hiểu rõ hơn về chúng.

– Prefix: Biểu thức tiền tố được biểu diễn bằng cách đặt toán tử lên trước các toán hạng. Cách biểu diễn này còn được biết đến với tên gọi “ký pháp Ba Lan” do nhà toán học Ba Lan Jan Łukasiewicz phát minh năm 1920. Với cách biểu diễn này, thay vì viết x+y như dạng trung tố, ta sẽ viết +xy. Tùy theo độ ưu tiên của toán tử mà chúng sẽ được sắp xếp khác nhau, bạn có thể xem một số ví dụ ở phía sau phần giới thiệu này.

– Postfix: Ngược lại với cách Prefix, tức là các toán tử sẽ được đặt sau các toán hạng. Cách biểu diễn này được gọi là “ký pháp nghịch đảo Ba Lan” hoặc được viết tắt là RPN (Reverse Polish notation), được phát minh vào khoảng giữa thập kỷ 1950 bởi một triết học gia và nhà khoa học máy tính Charles Hamblin người Úc.

Một số ví dụ:

Phương pháp chuyển từ biểu thức trung tố sang hậu tố

Độ ưu tiên của các toán tử

Một trong những điều quan trọng trước khi bắt đầu là phải tính toán được độ ưu tiên của các toán tử trong biểu thức nhập vào. Để đơn giản ta chỉ xét các toán tử hai ngôi và thường dùng bao gồm: multiply (+),subtract (-), multiply (), divide (/). Theo đó các toán tử “*, /” có cùng độ ưu tiên và cao hơn hai toán tử “+, -”. Như vậy ta có phương thức lấy độ ưu tiên toán tử như sau:

public int priority(char c){ // thiet lap thu tu uu tien if(c == '+'|| c == '-') return 1; else if(c == '*'|| c == '/') return 2; else return 0; }

Kiểm tra toán tử và toán hạng

Trong thuật toán chuyển đổi này ta cần có các phương thức kiểm tra xem một thành phần của chuỗi có phải là toán tử hoặc toán hạng không. Thay vì sử dụng các cấu trúc if hoặc switch dài dòng và bất tiện khi phát triển, ta sẽ dùng Regex để kiểm tra. Ngoài ra vì chuỗi nhập vào là một biểu thức đại số, nên các toán hạng ta sẽ xét không chỉ là các chữ số mà còn có chữ cái từ a-z và A-Z. Có một quy tắc nữa là khi dùng chữ cái thì chỉ cho phép duy nhất một chữ cái đại diện cho một toán hạng, còn khi dùng chữ số thì có thể nhiều chữ số ghép thành một toán hạng.

public boolean isOperator(char c){ // kiem tra xem co phai toan tu

    char operator[] = { '+', '-', '*', '/', ')', '(' };
    Arrays.sort(operator);
    if (Arrays.binarySearch(operator, c) > -1)
        return true;
    else return false;
}

Chuẩn hóa biểu thức Infix trước khi chuyển đổi

Các biểu thức Infix khi nhập vào có thể dư thừa các khoảng trắng, các kí tự không phù hợp hoặc viết sai cú pháp. Phần này các bạn xem bài chuẩn hóa xâu trong Java

Ngoài ra các bạn còn phải ghép các chữ số liền nhau thành số (toán hạng), tách các toán tử, phân cách với nhau bằng một khoảng trắng. Các phần tử này tôi sẽ gọi là một token.

Thuật toán chuyển đổi biểu thức từ trung tố sang hậu tố:

−

Nếu gặp 1 toán hạng (con số hoặc biến) thì nó ghi vào kết quả(chuỗi kết quả là biểu thức trung tố).

−

Nếu gặp dấu mở ngoặc thì đưa nó vào stack.

−

Nếu gặp 1 toán tử (ví dụ là t1) thì thực hiện 2 bước sau:

o

Nếu stack không rỗng, hoặc còn toán tử t2 ở đỉnhngăn xếp và độ ưu tiên của t1 nhỏ hơn hay bằng độ ưutiên của t2 thì lấy t2 ra khỏi ngăn xếp và ghi vào kết quả.

o

Nếu stack rỗng hoặc toán tử t2 ở đỉnh stack có độưu tiên thấp hơn t1 thì ghi (push) t1 vào ngăn xếp

−

Nếu gặp dấu đóng ngoặc thì cứ lấy các tất cả các toán tửtrong ngăn xếp ra và ghi vào kết quả cho đến khi lấy được dấumở ngoặc ra khỏi ngăn xếp.

−

Khi đã duyệt hết biểu thức trung tố, lần lượt lấy tất cả toánhạng (nếu có) từ ngăn xếp và ghi vào chuỗi kết quả.

Ví dụ:

chuyển đổi biểu thức trung tố sau sang hậu tố:3+4*2/(1-5)Kết quả là: 3 4 2 * 1 5 - / +

Quá trình làm việc của thuật toán như sau:

Ký tựStack Trình tự làm việcKết quả3{Empty}Đầu vào là 1 toánhạng (số) nênchương trình ghivào kết quả3++Do stack rỗng vàtoán tử “+” ở đỉnh stack nên ghitoán tử “+” vàongăn xếp34+Toán hạng tiếptheo nên vẫn đưara kết quả3 4*+ *Toán tử “+” ở đỉnh stack có độưu tiên thấp hơntoán tử “*” nên“*” được ghi vào3 4

1