Iseng: Infix to Postfix Converter dan Postfix Evaluator dalam Bahasa Java

Tulisan ini adalah kelanjutan dari 2 post sebelumnya (post1, post2). Post ini akan membahas mengenai algoritma konversi ekspresi infiks (ekspresi matematika dengan bentuk 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

1. Buatlah sebuah stack operator kosong
2. Masukkan ekspresi infiks yang akan dikonversi
3. 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
4. Ulangi langkah 3 hingga token habis
5. Pop terus stack operator sampai kosong dan tambahkan sebagai notasi posfiks

Algoritma Evaluasi Ekspresi Posfiks

1. Buatlah sebuah stack operan kosong
2. 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
3. Push hasil perhitungan ke dalam stack operan
4. Ulangi langkah 1 dan 2 hingga token habis
5. Pop stack operan dan kembalikan sebagai hasil evaluasi

Sementara itu implementasinya dalam Bahasa Java adalah,

/**
 *	@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<character> stackOfOperator;
	private MyStack<double> stackOfOperand;

	public MyInfixToPostfix() {
		stackOfOperator = new MyStack<character>();
		stackOfOperand = new MyStack<double>();
	}

	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 {
					/*
					 stack operator sudah ada isinya
					 ambil puncak stack, lalu bandingkan presedensinya dengan currentToken
					 jika precendence(puncak) > precedence(currentToken) maka pop stack
					*/
					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

Pemanggilan Program MyInfixToPostfix

Sampai di sini dulu tulisan saya tentang konversi ekspresi infiks ke posfiks dan juga evaluasi ekspresi posfiks. Semoga tulisan ini berguna bagi Anda

-KnightDNA-