Konversi Ekspresi Infix ke Ekspresi Postfix Menggunakan Konsep Queue Pada Java

Designed by Freepik

Queue

Queue merupakan salah satu jenis struktur data linier yang berbentuk antrian, dimana ketika data pertama kali masuk, akan selalu ditempatkan di posisi paling akhir. Queue menggunakan prinsip FIFO (First In First Out), dimana data yang pertama kali masuk akan dilayani/dioperasikan terlebih dahulu sebelum dikeluarkan.

Ekspresi Infix

Ekspresi infix merupakan bentuk ekspresi aritmatika yang biasa kita jumpai, dimana beberapa operand dilakukan suatu operasi menggunakan operator (+, -, *, /, ^) yang diletakkan diantara dua buah operand. Sebagai contoh yaitu ekspresi a + (b * c) berarti kita melakukan operasi perkalian pada operand pertama, yaitu b, dengan operand kedua, yaitu c, dimana hasilnya dijadikan sebagai operand kedua dari operasi berikutnya, yaitu operasi penjumlahan dengan operand pertama yaitu a.

Ekspresi Postfix

Walaupun bentuk ekspresi infix sangat mudah dipahami dan dievaluasi oleh manusia, tetapi ekspresi ini tidak bisa dipahami oleh komputer secara langsung, karena komputer tidak bisa secara langsung menentukan secara pasti operasi mana yang harus dikerjakan terlebih dahulu. Oleh karena itu, perlu adanya bentuk ekspresi lain yang dapat dipahami oleh komputer, yaitu ekspresi postfix. Pada operasi postfix, suatu operator tidak diletakkan di antara dua operator, melainkan berada di belakang operator. Sebagai contoh yaitu ketika kita memiliki bentuk ekspresi infix a + b , ketika dikonversi menjadi ekspresi postfix akan menjadi ab+.

Program Konversi Ekspresi Infix ke Ekspresi Postfix

Berikut ini merupakan program implementasi queue dan stack sebagai basis struktur data yang akan digunakan :

	package assignment_05;
	/**
	* This class represents queue data structure
	*
	* @author Fajar Zuhri Hadiyanto
	* @version 1.0
	* @since April 21st 2021
	*
	* @param <E> type of each element
	* */
	public class Queue<E> {
	/** Field to contain main list */
	private final E[] queue;
	/** Field to contain capacity of the queue*/
	private final int capacity;
	/** Field to contain front index of the queue */
	private int front;
	/** Field to contain rear index of the queue */
	private int rear;
	/** Field to contain current size of the queue */
	private int currentSize;
	/**
	* Constructor to initiate the queue
	* */
	public Queue(int capacity) throws IllegalArgumentException {
	if (capacity < 1) {
	throw new IllegalArgumentException("Capacity must be non zero positive integer");
	}
	this.front = 0;
	this.rear = -1;
	this.capacity = capacity;
	this.queue = (E[]) new Object[capacity];
	this.currentSize = 0;
	}
	/**
	* This method is used to check if the queue is full or not
	*
	* @return true if current size is equal to the capacity, else false
	* */
	public boolean isFull() {
	return this.currentSize == this.capacity;
	}
	/**
	* This method is used to check if the queue is empty or not
	*
	* @return true if current size is equal to 0, else false
	* */
	public boolean isEmpty() {
	return currentSize == 0;
	}
	/**
	* This method is used to insert new data to the queue
	*
	* @param data data to be inserted to the queue
	* @throws IllegalStateException when the queue is full
	* */
	public void enqueue(E data) throws IllegalStateException {
	if (isFull()) {
	throw new IllegalStateException("Queue is full !!!");
	} else {
	rear++;
	if (rear == capacity) rear = 0;
	queue[rear] = data;
	currentSize++;
	}
	}
	/**
	* This method is used to pull out front element of the queue
	*
	* @throws IllegalStateException when the queue is empty
	* */
	public void dequeue() throws IllegalStateException {
	if (isEmpty()) {
	throw new IllegalStateException("Queue is empty !!!");
	}
	front++;
	if (front == capacity) front = 0;
	currentSize--;
	}
	/**
	* This method is used to get value of the front element of the queue
	*
	* @throws IllegalStateException when the queue is empty
	* @return value of the front element of the queue
	* */
	public E front() throws IllegalStateException {
	if (isEmpty()) {
	throw new IllegalStateException("Queue is empty !!!");
	}
	return this.queue[front];
	}
	/**
	* This method is used to convert queue instance to string
	*
	* @return string representation of the queue
	* */
	@Override
	public String toString(){
	StringBuilder result = new StringBuilder("");
	while(!this.isEmpty()){
	result.append(this.front());
	this.dequeue();
	}
	return result.toString();
	}
	}

view raw Queue.java hosted with ❤ by GitHub

	package assignment_05;
	import java.util.ArrayList;
	import java.util.List;
	/**
	* This class represents stack data structure
	*
	* @author Fajar Zuhri Hadiyanto
	* @version 1.0
	* @since April 21st 2021
	*
	* @param <type> type of each element
	* */
	public class Stack<type> {
	/** Field to contain main list */
	private final List<type> list;
	/** Field to contain peak index */
	private int currentIndex;
	/**
	* Constructor to initiate the list and current index
	* */
	public Stack() {
	this.list = new ArrayList<>();
	this.currentIndex = -1;
	}
	/**
	* This method is used to add new data to the top of the list
	*
	* @param data value for the new data
	* */
	public void push(type data) {
	this.list.add(data);
	currentIndex++;
	}
	/**
	* This method is used to delete last data from the list
	*
	* @return value of the last element of the list
	* */
	public type pop() {
	type object = this.list.remove(currentIndex);
	currentIndex--;
	return object;
	}
	/**
	* This method is used to get the number of element in the list
	*
	* @return size of the list
	* */
	public int count() { return this.list.size(); }
	/**
	* This method is used to get value of the last element in the list
	*
	* @return value of the last element in a list
	* */
	public type peek() { return list.get(currentIndex); }
	/**
	* This method is used to remove all elements from the list
	* */
	public void clear() {
	this.list.clear();
	currentIndex = -1;
	}
	}

view raw Stack.java hosted with ❤ by GitHub

Berikut ini program utama yang menjalankan konversi ekspresi infix ke postfix :

	package assignment_05;
	/**
	* This class represents expression converter between infix and postfix
	*
	* @author Fajar Zuhri Hadiyanto
	* @version 1.0
	* @since April 21st 2021
	* */
	public class ExpressionConverter {
	/**
	* This method is used to get the precedence level of the operator
	*
	* @param operator operator to be looked for the precedence level
	* @return precedence level of the operator
	* */
	private static int precedence(char operator){
	switch (operator) {
	case '+':
	case '-':
	return 1;
	case '*':
	case '/':
	case '%':
	return 2;
	case '^':
	return 3;
	default:
	return -1;
	}
	}
	/**
	* This method is used to convert infix expression to postfix expression
	*
	* @param expression infix expression to be converted
	* @return postfix expression
	* */
	public static String infixToPostfix(String expression) {
	// PREPARE NEW STACK FOR OPERATOR AND
	// QUEUE FOR THE FINAL RESULT
	Stack<Character> operator = new Stack<>();
	Queue<Character> result = new Queue<>(expression.length());
	// REPEAT FOR EACH CHARACTER IN THE EXPRESSION
	for (char a: expression.toCharArray()) {
	// IF CHARACTER IS A LETTER OR A DIGIT ...
	if(Character.isLetterOrDigit(a)) {
	// ... JUST PUSH IT TO THE FINAL RESULT QUEUE
	result.enqueue(a);
	}
	// IF CHARACTER IS AN OPENING PARENTHESES ...
	else if(a == '(') {
	// ... PUSH IT TO THE OPERATOR STACK
	operator.push(a);
	}
	// IF CHARACTER IS A CLOSING PARENTHESES ...
	else if(a == ')') {
	// ... MOVE ALL OPERATORS BETWEEN THIS CLOSING AND
	// NEAREST OPENING PARENTHESES TO THE FINAL RESULT QUEUE ...
	while(operator.count() != 0 && operator.peek() != '(') {
	result.enqueue(operator.pop());
	}
	// ... AND ALSO THROW THE OPENING PARENTHESES
	operator.pop();
	}
	// IF CHARACTER IS AN ARITHMETIC OPERATOR ...
	else {
	// ... MOVE ALL OPERATORS IN STACK THAT HAVE
	// PRECEDENCE LOWER OR EQUAL TO THIS OPERATOR ...
	while(operator.count() != 0 && precedence(a) <= precedence(operator.peek())) {
	result.enqueue(operator.pop());
	}
	// ... THEN, PUSH THE CHARACTER TO THE STACK
	operator.push(a);
	}
	}
	// MOVE THE REST OPERATORS TO THE QUEUE
	while(operator.count() != 0) {
	if(operator.peek() == '(') {
	return "Invalid Expression";
	}
	result.enqueue(operator.pop());
	}
	// CONVERT QUEUE TO STRING, THEN RETURN IT
	return result.toString();
	}
	}

view raw ExpressionConverter.java hosted with ❤ by GitHub

Berikut ini program yang menjadi aplikasi konsol untuk menjalankan program konversi :

	package assignment_05;
	import java.util.Scanner;
	/**
	* This class is used as main console application
	*
	* @author Fajar Zuhri Hadiyanto
	* @version 1.0
	* @since April 21st 2021
	* */
	public class QueueApplication {
	/**
	* This is used as main method
	*
	* @param args arguments to the console app while compiled and launched.
	* */
	public static void main(String[] args) {
	// PREPARATION
	String input, output;
	Scanner scanner = new Scanner(System.in);
	// GET THE INFIX EXPRESSION
	System.out.print("Input the infix expression : ");
	input = scanner.nextLine();
	// CONVERT INFIX TO POSTFIX EXPRESSION
	output = ExpressionConverter.infixToPostfix(input);
	// DISPLAY BOTH INFIX AND POSTFIX EXPRESSION
	System.out.println("Infix Expression : " + input);
	System.out.println("Postfix Expression : " + output);
	}
	}

view raw QueueApplication.java hosted with ❤ by GitHub

Ketika method main pada class QueueApplication dijalankan, maka hasilnya akan menjadi seperti berikut :

Source code dari program di atas dapat diakses di sini

Reference :

• https://www.geeksforgeeks.org/stack-set-2-infix-to-postfix/