a op b
, di mana a
dan b
adalah operan dan op
adalah operator) ke posfiks (ekspresi matematika dengan bentuk a b op
). Saya memanfaatkan StringTokenizer bawaan Java untuk mengambil setiap operator dan operan pada ekspresi infiks sebagai masukan, serta koleksi objek stack generik yang dibuat dari 2 post sebelumnya.Algoritma Konversi Ekspresi Infiks ke Posfiks
- Buatlah sebuah stack operator kosong
- Masukkan ekspresi infiks yang akan dikonversi
- Ambil setiap token pada ekspresi infiks, lalu periksa setiap token
- Jika token adalah operan, maka tambahkanlah sebagai notasi posfiks
- Jika token adalah tanda kurung buka, maka push tanda kurung buka ke stack operator
- Jika token adalah tanda kurung tutup, maka pop terus stack operator sampai bertemu tanda kurung buka
- Jika token adalah operator, periksalah stack operator
- Jika stack kosong, maka push token ke dalam stack operator
- Jika stack ada isinya, maka bandingkan presedensi puncak stack dengan token
- Jika presedensi lebih besar maka pop stack operator dan tambahkanlah sebagai notasi posfiks
- Push token ke stack operator
- Ulangi langkah 3 hingga token habis
- Pop terus stack operator sampai kosong dan tambahkan sebagai notasi posfiks
Algoritma Evaluasi Ekspresi Posfiks
- Buatlah sebuah stack operan kosong
- Ambil setiap token pada ekspresi posfiks, lalu periksa setiap token
- Jika token adalah operan, maka push token ke dalam stack operan
- Jika token adalah operator, maka pop stack operan lalu simpan sebagai operan kedua, dan pop lagi stack operan lalu simpan sebagai operan pertama.
- Lakukan perhitungan terhadap kedua operan sesuai dengan operator token
- Push hasil perhitungan ke dalam stack operan
- Ulangi langkah 1 dan 2 hingga token habis
- Pop stack operan dan kembalikan sebagai hasil evaluasi
Sementara itu implementasinya dalam Bahasa Java adalah sebagai berikut,
/** * @author Aprian Diaz Novandi (13505102) * @version 2.0 * @since 13 September 2008 * @see MyStack * @throws MyInfixToPostfixException * Implementasi kelas yang mengubah ekspresi masukan infix ke postfix dan melakukan evaluasi terhadap ekspresi postfix */ import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.lang.Double; import java.lang.Math; import java.util.StringTokenizer; import MyCollection.*; public class MyInfixToPostfix { private MyStack stackOfOperator; private MyStack stackOfOperand; public MyInfixToPostfix() { stackOfOperator = new MyStack(); stackOfOperand = new MyStack(); } public boolean isOperator(String token) { return (token.equalsIgnoreCase("^") || token.equalsIgnoreCase("*") || token.equalsIgnoreCase("/") || token.equalsIgnoreCase("%") || token.equalsIgnoreCase("+") || token.equalsIgnoreCase("-")); } public boolean isOperand(String token) { //sudah menangani kasus bilangan negatif return (!isOperator(token) && ((Character.isDigit(token.charAt(0))) || (token.charAt(0) == '-'))); } //mengembalikan prioritas operator saat evaluasi public int precedence(char opr) { int retval; switch (opr) { case '^': { retval = 3; break; } case '*': { retval = 2; break; } case '/': { retval = 2; break; } case '%': { retval = 2; break; } case '+': { retval = 1; break; } case '-': { retval = 1; break; } default: { retval = 0; break; } } return retval; } public String convertToPostfix(String infixExp) throws Exception, MyInfixToPostfixException { StringTokenizer st = new StringTokenizer(infixExp); String curToken = "", postfixExp = ""; int nKurungBuka = 0, nKurungTutup = 0; Character temp; while(st.hasMoreTokens()) { //mengambil token curToken = st.nextToken(); if(isOperand(curToken)) { //jika currentToken adalah operand, maka kembalikan sebagai ekspresi postfix postfixExp = postfixExp + " " + (Double.parseDouble(curToken)); } else if(curToken.equals("(")) { //jika currentToken adalah kurung buka, maka push tanda kurung buka ke stack operator Character opr = new Character('('); stackOfOperator.push(opr); nKurungBuka++; } else if(curToken.equals(")")) { //jika currentToken adalah kurung tutup, maka pop stack operator sampai ketemu kurung buka while(((Character)stackOfOperator.peek()).charValue() != '(') { postfixExp = postfixExp + " " + stackOfOperator.pop(); } temp = stackOfOperator.pop(); nKurungTutup++; } else if(isOperator(curToken)) { //jika currentToken adalah operator if(stackOfOperator.isEmpty()) { //stack operator masih kosong, maka push currentToken ke stack operator Character opr = new Character(curToken.charAt(0)); stackOfOperator.push(opr); } else { Character opr = new Character(curToken.charAt(0)); if (precedence(((Character)stackOfOperator.peek()).charValue()) > precedence(opr)) { postfixExp = postfixExp + " " + stackOfOperator.pop(); } //push currentToken stackOfOperator.push(opr); } } else { //ekspresi tidak valid throw new MyInfixToPostfixException("Ekspresi tidak valid"); } } //ekspresi tidak valid if(nKurungBuka != nKurungTutup) throw new MyInfixToPostfixException("Ekspresi tidak valid"); //pop terus stack operator sampai kosong while (!stackOfOperator.isEmpty()) { postfixExp = postfixExp + " " + stackOfOperator.pop(); } return postfixExp; } public double evaluate(String postfixExp) throws Exception { StringTokenizer st = new StringTokenizer(postfixExp); double retval; String curToken = ""; while (st.hasMoreTokens()) { //mengambil token curToken = st.nextToken(); if(isOperand(curToken)) { //jika currentToken adalah operand, maka push ke stack operand Double opn = new Double(Double.parseDouble(curToken)); stackOfOperand.push(opn); } else { //jika currentToken adalah operator, maka evaluasi dua operan sebelumnya double opn2 = ((Double)stackOfOperand.pop()).doubleValue(); double opn1 = ((Double)stackOfOperand.pop()).doubleValue(); double result = 0; switch(curToken.charAt(0)) { case '*': { result = opn1 * opn2; break; } case '+': { result = opn1 + opn2; break; } case '-': { result = opn1 - opn2; break; } case '/': { result = opn1 / opn2; break; } case '%': { result = opn1 % opn2; break; } case '^': { result = Math.pow(opn1, opn2); break; } } Double opn = new Double(result); stackOfOperand.push(opn); } } retval = ((Double)stackOfOperand.pop()).doubleValue(); return retval; } public static void main(String args[]) throws Exception { String infixExp = "", postfixExp = ""; MyInfixToPostfix itp = new MyInfixToPostfix(); System.out.println("PERHATIAN!"); System.out.println("Pisahkah masing-masing operand dan operator (termasuk kurung buka dan tutup) dengan minimal satu buah spasi"); System.out.println("--------------------------------------------------\n"); try { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); System.out.print("Masukkan ekspresi infix: "); infixExp = br.readLine(); postfixExp = itp.convertToPostfix(infixExp); System.out.println("Ekspresi postfix: " + postfixExp); System.out.println("Hasil evaluasi: " + itp.evaluate(postfixExp)); } catch (Exception e) { e.printStackTrace(); } finally { System.out.println("--------------------------------------------------\n"); } } } /** * @see java.lang.Exception */ class MyInfixToPostfixException extends Exception { private String message; public MyInfixToPostfixException(String _message) { super(_message); message = _message; } public String getMessage() { return message; } public String toString() { return "MyInfixToPostfixException: " + getMessage(); } public void printStackTrace() { System.out.println(this); super.fillInStackTrace(); } }
Di bawah ini adalah contoh pemanggilan programnya
Sampai di sini dulu tulisan saya tentang konversi ekspresi infiks ke posfiks dan juga evaluasi ekspresi posfiks. Semoga tulisan ini berguna bagi Anda :)
-KnightDNA-