[Thuật Toán – Java] Chuyển Biểu Thức Trung Tố Sang Hậu Tố

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.

public String[] processString(String sMath){ // xu ly bieu thuc nhap vao thanh cac phan tu String s1 = "", elementMath[] = null; InfixToPostfix IFP = new InfixToPostfix(); sMath = sMath.trim(); sMath = sMath.replaceAll("s+"," "); // chuan hoa sMath for (int i=0; i<sMath.length(); i++){ char c = sMath.charAt(i);//sMath.substring(i,1); if (!IFP.isOperator(c)) s1 = s1 + c; else s1 = s1 + " " + c + " "; } s1 = s1.trim(); s1 = s1.replaceAll("s+"," "); // chuan hoa s1 elementMath = s1.split(" "); //tach s1 thanh cac phan tu //System.out.println(s1); return elementMath; }

Thuật toán để chuyển một biểu thức Infix sang dạn Prefix:

Đọc từng token trong biểu thức infix từ trái qua phải, với mỗi token ta thực hiện các bước sau: – Nếu là toán hạng: cho ra output. – Nếu là dấu mở ngoặc “(“: cho vào stack – Nếu là dấu đóng ngoặc “)”: lấy các toán tử trong stack ra và cho vào output cho đến khi gặp dấu mở ngoặc “(“. (Dấu mở ngoặc cũng phải được đưa ra khỏi stack) – Nếu là toán tử: +/Chừng nào ở đỉnh stack là toán tử và toán tử đó có độ ưu tiên lớn hơn hoặc bằng toán tử hiện tại thì lấy toán tử đó ra khỏi stack và cho ra output. +/Đưa toán tử hiện tại vào stack Sau khi duyệt hết biểu thức infix, nếu trong stack còn phần tử thì lấy các token trong đó ra và cho lần lượt vào output.

VD: Chúng ta sẽ chuyển biểu thức A*B+C*((D-E)+F)/G từ dạng Infix sang dạng Postfix:

Cài đặt trên Java

public String[] postfix(String[] elementMath){ InfixToPostfix IFP = new InfixToPostfix(); String s1 = "", E[]; Stack <String> S = new Stack <String>(); for (int i=0; i<elementMath.length; i++){ // duyet cac phan tu char c = elementMath[i].charAt(0); // c la ky tu dau tien cua moi phan tu if (!IFP.isOperator(c)) // neu c khong la toan tu s1 = s1 + " " + elementMath[i]; // xuat elem vao s1 else{ // c la toan tu if (c == '(') S.push(elementMath[i]); // c la "(" -> day phan tu vao Stack else{ if (c == ')'){ // c la ")" char c1; //duyet lai cac phan tu trong Stack do{ c1 = S.peek().charAt(0); // c1 la ky tu dau tien cua phan tu if (c1 != '(') s1 = s1 + " " + S.peek(); // trong khi c1 != "(" S.pop(); }while (c1 != '('); } else{ while (!S.isEmpty() && IFP.priority(S.peek().charAt(0)) >= IFP.priority(c)){ // Stack khong rong va trong khi phan tu trong Stack co do uu tien >= phan tu hien tai s1 = s1 + " " + S.peek(); // xuat phan tu trong Stack ra s1 S.pop(); } S.push(elementMath[i]); // dua phan tu hien tai vao Stack } } } } while (!S.isEmpty()){ // Neu Stack con phan tu thi day het vao s1 s1 = s1 + " " + S.peek(); S.pop(); } E = s1.split(" "); // tach s1 thanh cac phan tu return E; }