Programming in Java : Mengubah Ekspresi Infix menjadi Postfix

 

Apa itu Ekspresi Infix dan Postfix

Ekspresi Infix merupakan ekspresi yang digunakan jika operator (tanda +, -, *, /, ^) berada ditengah-tengah operand/variabel yang ingin dihitung. Ekspresi Infix merupakan ekspresi yang paling sering kita gunakan sehari-hari. Contoh ekspresi infix, yaitu :

1. a+b*c/d
2. (a^b)*c-d    

Berbeda dengan ekspresi infix, ekspresi postfix menuliskan operator setelah operand yang dimaksud telah dituliskan, misalnya kita akan menambahkan 'a' dengan 'b', kemudian kita mengalikan 'e' dengan 'd' baru mengurangi hasil setelahnya. Contoh berikut akan menunjukkan perbedaan ekspresi infix dan postfix.

    

    Ekspresi Infix     : a+b-(e*d)

    Ekspresi Postfix : ab+ed*-

Program untuk mengubah ekspresi Infix menjadi Postfix

Untuk mengubah ekspresi infix menjadi postfix dapat digunakan queue dan stack. Berikut merupakan class dari queue dan stack.

Queue Class

	/**
	* Queue Methods
	*
	* @author Anggito
	* @ver 1.0 - 22 Apr 21
	*/
	public class Queue<elements>
	{
	//Instance variable for queue
	private int capacity;
	int front;
	int rear;
	private elements queue[];
	private int currSize;
	//Constructor for Queue Object
	public Queue(int capacity) {
	this.capacity = capacity;
	front = 0;
	rear = -1;
	//queue capacity must be > 0
	if(capacity < 0) {
	throw new IllegalStateException("Queue Capacity must be more than zero");
	}
	else {
	queue = (elements[]) new Object[capacity];
	currSize = 0;
	}
	}
	//check if queue is empty
	public boolean isEmpty() {
	return (currSize == 0);
	}
	//check if queue is full
	public boolean isFull() {
	return (currSize == this.capacity);
	}
	//inserting new element to queue
	public void enqueue(elements newElement) {
	if(isFull())
	throw new IllegalStateException("Queue is Full!");
	else {
	rear++;
	//if capacity only 1
	//rear == front == 0
	if(rear == this.capacity - 1)
	rear = 0;
	queue[rear] = newElement;
	currSize++;
	}
	}
	//removing element from queue
	public void dequeue() {
	if(isEmpty())
	throw new IllegalStateException("Queue is Empty!");
	else {
	front++;
	//if capacity only 1
	if(front == this.capacity) {
	front = 0;
	}
	currSize--;
	}
	}
	//front element of queue
	public elements front() {
	if(isEmpty())
	throw new IllegalStateException("Queue is Empty!");
	else {
	return queue[front];
	}
	}
	//rear element of queue
	public elements rear() {
	if(isEmpty()) {
	throw new IllegalStateException("Queue is Empty!");
	}
	else {
	return queue[rear];
	}
	}
	@Override
	public String toString() {
	StringBuilder ansString = new StringBuilder("");
	while(!this.isEmpty()) {
	ansString.append(this.front());
	this.dequeue();
	}
	return ansString.toString();
	}
	}

view raw Queue.java hosted with ❤ by GitHub

Stack Class

	/**
	* Stack Methods
	*
	* @author Anggito Anju
	* @version 1.0 - 22 Apr 21
	*/
	import java.util.List;
	import java.util.ArrayList;
	public class Stack
	{
	private List<Object> list = new ArrayList<Object>();
	private int currIndex = -1;
	public void push(Object newData) {
	list.add(newData);
	currIndex++;
	}
	public Object pop() {
	Object popData = list.remove(currIndex);
	currIndex--;
	return popData;
	}
	public Object top() {
	return list.get(currIndex);
	}
	public void clearStack(Object newData) {
	list.clear();
	currIndex = -1;
	}
	public int size() {
	return list.size();
	}
	}

view raw Stack.java hosted with ❤ by GitHub

Pada program ini, stack akan menjadi tempat operator sementara, sedangkan queue digunakan untuk menyimpan operand.

Untuk mengubah ekspresi dari infix ke postfix akan digunakan class baru sebagai berikut

InfixtoPostfix Class

	/**
	* Converting infix to confix expressions
	*
	* @author Anggito Anju
	* @version 1.0 - 22 Apr 21
	*/
	import java.util.Stack;
	public class InfixtoPostfixClass
	{
	//check the operator's precedences
	static int precedence(char ch)
	{
	switch (ch)
	{
	case '+':
	case '-':
	return 1;
	case '*':
	case '/':
	return 2;
	case '^':
	return 3;
	}
	return -1;
	}
	//Converting Infix to Postfix expression
	//Main Method
	//String for infix in input parameter
	//String for postfix fro output
	static String infixToPostfix(String inputExpression) {
	/* Use Stack to store operators */
	//stack init
	Stack<Character> stackProcess = new Stack<>();
	/* Use Queue to store answer */
	//queu init
	//use input lenght to initialize queue max capacity
	Queue<Character> queueAnswer = new Queue<>(inputExpression.length());
	for(int i = 0; i<inputExpression.length(); i++) {
	char scannedInput = inputExpression.charAt(i);
	//if scanned character is letter or digit
	//add to queue
	if(Character.isLetterOrDigit(scannedInput))
	queueAnswer.enqueue(scannedInput);
	//if scanned character is '('
	//add to stack
	else if(scannedInput == '(')
	stackProcess.push(scannedInput);
	//if scanned character is ')'
	//move out all the stack elements till '(' is encountered to queue
	else if(scannedInput == ')') {
	while(!stackProcess.isEmpty() && stackProcess.peek() != '(') {
	queueAnswer.enqueue(stackProcess.pop());
	}
	//move '(' to queue
	queueAnswer.enqueue(stackProcess.pop());
	}
	//if scanned character is an operator
	else {
	//check till stack operators is > input operator
	//move out the operator to queue
	while(!stackProcess.isEmpty() && precedence(scannedInput) <= precedence(stackProcess.peek())) {
	queueAnswer.enqueue(stackProcess.pop());
	}
	//add the new bigger operator to stack
	stackProcess.push(scannedInput);
	}
	}
	//if all input string already processed
	//move all elements from stack to queue
	while(!stackProcess.isEmpty()) {
	//if there is '(' without ')'
	if(stackProcess.peek() == '(')
	throw new IllegalStateException("Invalid Expression");
	//move to queue
	queueAnswer.enqueue(stackProcess.pop());
	}
	//returning all queue elements to main methods
	return queueAnswer.toString();
	}
	}

view raw InfixtoPostfixClass.java hosted with ❤ by GitHub

Operator memiliki sifat khusus, seperti * dan / lebih didahulukan dari + dan -, dan sebagainya. Maka dari itu pada infixtoPostfix class dapat dibuat method precedence untuk mengatur hal ini.

Setelah operator dan ekspresi infix telah diatur dan diubah menjadi ekspresi postfix, jawaban masih tersimpan dalam queue. Untuk mengubah queue menjadi String sehingga dapat dikeluarkan output berupa String, maka dibuat method toString pada Queue.java sebagai berikut.

	public String toString() {
	StringBuilder ansString = new StringBuilder("");
	while(!this.isEmpty()) {
	ansString.append(this.front());
	this.dequeue();
	}
	return ansString.toString();
	}

view raw QueuetoString hosted with ❤ by GitHub

Setelah Queue telah menjadi String, String akan di return ke method main. Berikut contoh pengaplikasian program "Mengubah Ekspresi Infix menjadi Postfix" di Java.

	/**
	* App Infix to Postfix Expression
	*
	* @author Anggito Anju
	* @version 1.0 - 22 Apr 21
	*/
	import java.util.Scanner;
	public class AppInfixtoPostfix
	{
	public static void main(String args[]) {
	//input variable
	String inputExpressionUser;
	String outputAnswer;
	//inputing user expression
	Scanner scanner = new Scanner(System.in);
	inputExpressionUser = scanner.nextLine();
	scanner.close();
	//converting user expression
	outputAnswer = InfixtoPostfixClass.infixToPostfix(inputExpressionUser);
	System.out.println("Infix : " + inputExpressionUser);
	System.out.println("Postfix : " + outputAnswer);
	}
	}

view raw AppInfixtoPostfix.java hosted with ❤ by GitHub

Dan berikut merupakan contoh input dan output dari program