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-
Posts
