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

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-
blog comments powered by Disqus