PENUGASAN 5 -- QUEUE

 Konversi Infix ke Postfix dengan Menggunakan Queue

Notasi Matematika Prefix, Infix, dan Postfix

1. Prefix

Prefix adalah metode penulisan dengan meletakkan operator di depan operand dan tanpa menuliskan tanda kurung.

Contoh pemakaian prefix adalah  +AB, – +ABC, * + AB – CD.

2. Infix

Infix adalah cara penulisan ungkapan dengan meletakkan operator di antara dua operand dalam hal ini pemakaian tanda kurung sangat menentukan hasil operasi.

Contoh pemakaian infix adalah A+B, A+B-C, (A+B)*(C-D).

3. Postfix

Postfix adalah metode penulisan dengan menuliskan operator setelah operand dan tanpa menuliskan tanda kurung.

Contoh penulisan sufix adalah AB + , AB + C – , AB + CD -*.

Konversi Infix ke Postfix

Konversi infix ke postfix dapat dilakukan dengan menggunakan stack ataupun queue.

1. Stack Class

/**
 * Write a description of class Stack here.
 *
 * @author Adelia Hasna Surya Putri
 * @version 27/04/2021
 */
 
public class Stack implements StackInterface {

ArrayList<Character> stack = new ArrayList<Character>();

public void push(char ch) {
    stack.add(ch);
}

public char top() {
    char myCh;
    myCh = stack.get(stack.size() - 1);
    return myCh;
}

public char pop() {
    char myCh;
    myCh = stack.get(stack.size() - 1);
    stack.remove(stack.get(stack.size() - 1));
    return myCh;
}

public boolean ismt() {
    boolean retval = true;
    retval = stack.isEmpty();
    return retval;
}

}

2. Queue

/**
 * Write a description of Queue stack here.
 *
 * @author Adelia Hasna Surya Putri
 * @version 27/04/2021
 */
 
public class Queue implements QueueInterface {

ArrayList<Character> que = new ArrayList<Character>();

@Override
public void add2Rear(char ch) { // add element to rear of queue
    que.add(ch);

}

@Override
public char removeFront() { // returns first element AND removes it
    char retval = '1';
    retval = que.remove(0);
    return retval;
}

@Override
public char front() { // returns first element
    char retval = '1';
    retval = que.get(0);
    return retval;
}

@Override
public boolean ismtQ() { // true: if empty, false: if otherwise
    boolean retval = true;
    retval = que.isEmpty();
    return retval;
}

}

3. Konversi ifix ke postfix

/**
 * Write a description of class InfixToPostFix here.
 *
 * @author Adelia Hasna Surya Putri
 * @version 27/04/2021
 */
 
import java.util.Stack;

public class InfixToPostFix {

    static int precedence(char c){
        switch (c){
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
                return 2;
            case '^':
                return 3;
        }
        return -1;
    }

    static String infixToPostFix(String expression){

        String result = "";
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i <expression.length() ; i++) {
            char c = expression.charAt(i);

            //check if char is operator
            if(precedence(c)>0){
                while(stack.isEmpty()==false && precedence(stack.peek())>=precedence(c)){
                    result += stack.pop();
                }
                stack.push(c);
            }else if(c==')'){
                char x = stack.pop();
                while(x!='('){
                    result += x;
                    x = stack.pop();
                }
            }else if(c=='('){
                stack.push(c);
            }else{
                //character is neither operator nor ( 
                result += c;
            }
        }
        for (int i = 0; i <=stack.size() ; i++) {
            result += stack.pop();
        }
        return result;
    }

    public static void main(String[] args) {
        String exp = "(a+b/c)*d-(e*f*g)";
        System.out.println("Infix Expression: " + exp);
        System.out.println("Postfix Expression: " + infixToPostFix(exp));
    }
}

 

Output:

Referensi

https://anitarahmasyafitri97.wordpress.com/queue/

https://kuliahinformatika.wordpress.com/2010/02/06/stack-queue-penjelasan-beserta-contoh-metode-prefix-infix-dan-postfix/

Adelia Hasna Surya Putri/5025201200