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



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

-KnightDNA-

Iseng: Linked-List Generik dan Stack Generik dengan Representasi Linked-List dalam Bahasa Java (bagian II)

Lanjutan dari post sebelumnya.

Sekarang adalah kelas Stack dan StackException (letakkan keduanya sebagai dua kelas public di dua file yang berbeda)

/**
 *    @author     Aprian Diaz Novandi (13505102)
 *    @version    1.0
 *    @since      13 September 2008
 *    @see        MyList
 *    @throws     MyStackException
 *    Implementasi kelas stack dengan representasi linked-list di Java
 */

package MyCollection;

public class MyStack extends MyList {
    //ukuran stack
    private int size;

    //puncak stack
    private ElmtList top;

    //ctor
    public MyStack() {
        super();
        top = first;
        size = 0;
    }

    public boolean isEmpty() {
        return top == null;
    }

    public int getSize() {
        return size;
    }

    public T peek() {
        return top.getInfo();
    }

    public void push(T item) {
        ElmtList node = new ElmtList(item);
        super.insertFirst(node);
        top = first;
        size++;
    }

    public T pop() throws MyStackException {
        T item = null;
        if(isEmpty()) {
            throw new MyStackException("Stack kosong");
        } else {
            ElmtList node = super.deleteFirst();
            item = node.getInfo();
            top = first;
            size--;
        }
        return item;
    }

    public String toString() {
        String retval = super.toString();
        return retval;
    }
}

package MyCollection;

public class MyStackException extends Exception {
    private String message;

    public MyStackException(String _message) {
        super(_message);
        message = _message;
    }

    public String getMessage() {
        return message;
    }

    public String toString() {
        return "MyStackException: " + getMessage();
    }

    public void printStackTrace() {
        System.out.println(this);
        super.fillInStackTrace();
    }
}

Selanjutnya kelas StackDriver untuk pengujian

import MyCollection.MyStack;
import MyCollection.MyStackException;

public class MyStackDriver {
    public static void main(String[] args) {
        MyStack S1 = new MyStack();
        MyStack S2 = new MyStack();
        try {
            S1.push(100);
            S1.push(101);
            S1.push(102);
            S2.push('(');
            int item = S1.pop();
            int itemTop = S1.peek();
            System.out.println("Item yang di-pop: " + item);
            System.out.println("Item di top of stack: " + itemTop);
        } catch (MyStackException e) {
            e.printStackTrace();
        } finally {
            System.out.println(S1);
            System.out.println(S2);
        }
    }
}

Oke, itu dulu keisengan saya di sela kebosanan mengerjakan TA untuk bagian pertama ini. Sampai jumpa di postingan saya selanjutnya tentang InfixToPostfix. Doakan TA saya lancar ya :D. Semoga berguna bagi Anda.

-KnightDNA-

Iseng: Linked-List Generik dan Stack Generik dengan Representasi Linked-List dalam Bahasa Java (bagian I)

Iseng-iseng ingin menambah daftar post, kali ini saya akan menyisipkan salah satu tugas mata kuliah S2 di Rekayasa Perangkat Lunak, IF-ITB. Mata kuliahnya Algoritma dan Pemrograman. Ya, sepintas namanya sama dengan mata kuliah yang pernah saya ambil saat tingkat satu kemarin, tapi ternyata setelah sang dosen (Pak Saiful) memberikan silabus kuliahnya tampaklah bahwa mata kuliah ini adalah lanjutan (lebih tepatnya ulangan dengan sudut pandang ala mahasiswa S2) dari trilogi pemrograman IF ITB (Algoritma dan Pemrograman, Algoritma dan Struktur Data, dan Pemrograman Beriorentasi Objek).

Materinya, karena masih awal-awal, banyak yang me-review kuliah S1 kemarin, termasuk tugas-tugasnya. Kebetulan tugas minggu ini adalah review OOP yang terkait dengan materi koleksi objek dan kelas generik. Judul post ini adalah tugasnya, dan sebenarnya akan dipakai untuk membuat kelas yang akan mengubah notasi operasi matematika infiks menjadi posfiks, lalu melakukan evaluasi terhadap notasi posfiks tadi dengan menggunakan stack. Tapi stack-nya harus dalam representasi linked-list.

Sebenarnya di Java sudah ada kelas-kelas koleksi objek tersebut (List, Stack, dan Queue/tidak dibahas di post ini) milik API Java, tapi pak dosen menyarankan mahasiswanya untuk mengkode sendiri koleksi objek yang diperlukan dalam tugas. So, here it is. Mudah-mudahan berguna bagi adik-adik tingkat saya yang nantinya akan mengambil kuliah Pemrograman Beriorientasi Objek atau siapa pun yang ingin mencoba-coba. Just correct me if I'm wrong!

/**
 *    @author     Aprian Diaz Novandi (13505102)
 *    @version    3.0
 *    @since      13 September 2008
 *    Implementasi kelas linked-list generic di Java
 */

package MyCollection;

import java.lang.NullPointerException;

public class MyList {
    static class ElmtList {
        //data
        private T info;
        //referensi ke elemen selanjutnya
        private ElmtList next;

        public ElmtList() {
            info = null;
        }

        public ElmtList(T _info) {
            info = _info;
        }

        public T getInfo() {
            return info;
        }

        public ElmtList getNext() throws NullPointerException {
            return next;
        }

        public void setNext(ElmtList node) throws NullPointerException {
            next = node;
        }

        public String toString() {
            if(next == null)
                return "[" + info + "|X]";
            else
                return "[" + info + "]->";
        }
    }

    //elemen pertama list
    protected ElmtList first;

    //ctor
    public MyList() { }

    public boolean isEmpty() {
        return first == null;
    }

    public ElmtList getFirst() {
        return first;
    }

    public void insertFirst(ElmtList node) {
        node.setNext(first);
        first = node;
    }

    public void insertLast(ElmtList node) {
        if(first == null)
            first = node;
        else {
            ElmtList P = first;
            while(P.getNext() != null) {
                P = P.getNext();
            }
            P.setNext(node);
        }
    }

    public ElmtList deleteFirst() {
        ElmtList node = first;
        if(node != null) {
            first = node.getNext();
            node.setNext(null);
        }
        return node;
    }

    public ElmtList deleteLast() {
        ElmtList P = first, Prev = null, retval = null;
        if (P == null) {
            //list kosong
            retval = null;
        } else if(P.getNext() == null) {
            //elemen list hanya satu
            first = null;
            retval = P;
        } else {
            while(P.getNext() != null) {
                Prev = P;
                P = P.getNext();
            }
            retval = P;
            Prev.setNext(null);
            P = Prev;
        }
        return retval;
    }

    public String toString() {
        ElmtList P = first;
        String retval = "";
        while(P.getNext() != null) {
            //cetak dan telusuri semua elemen
            retval += P.toString();
            P = P.getNext();
        }
        //cetak elemen terakhir
        retval += P.toString();
        return retval;
    }

    //driver, untuk pengujian
    public static void main(String[] args) {
        MyList L1 = new MyList();
        MyList L2 = new MyList();

        try {
            L1.insertFirst(new ElmtList(100));
            L1.insertFirst(new ElmtList(101));
            L1.insertFirst(new ElmtList(102));
            L1.deleteFirst();
            L2.insertFirst(new ElmtList("aku"));
            L2.insertFirst(new ElmtList("kamu"));
            L2.insertLast(new ElmtList("dia"));
            L2.insertLast(new ElmtList("mereka"));
            L2.deleteFirst();
            L2.deleteLast();
        } catch (NullPointerException e) {
            e.printStackTrace();
        } finally {
            System.out.println(L1);
            System.out.println(L2);
        }
    }
}

Bersambung.

-KnightDNA-

PS: Saya mengelompokkan koleksi-koleksi objek tadi dalam satu package bernama MyCollection