Infix to Postfix

Hello, guys!

Well, hello there! It's been a while since I posted an article about my assignment due to some days off. Okay, so without any further due, i'm just going to get down to the business. While the last article was mostly talking about stack, now we're going to discuss about one of its application, which is the translation from infix to postfix.  

Now the question is how? To answer this complicated question, let's just check out the article I've written down here!

Menerjemahkana Infix ke Postfix

Bagaimana Manusia Mengerjakan Operasi Infix?

    Dalam mengerjakan sebuah operasi aritmatika, biasanya manusia mengikuti beberapa langkah sederhana sebagai berikut. Pertama, mereka akan membacanya dari kiri ke kanan. Kemudian ketika manusia sudah membaca cukup data berupa 2 variabel dan sebuah operasi, maka mereka akan menghitungnya dan menyimpan jawaban tersebut. Proses ini dilakukan secara berulang-ulangーdari kiri ke kanan dan mengerjakannya ketika memungkinkanーsampai akhir dari persoalan.

        Dalam mengerjakan operasi infix aritmatika, seorang manusia akan bergerak maju dan mundur sepanjang persoalannya. Ia akan bergerak maju (kiri ke kanan) membaca variabel dan operatornya. Ketika ia mendapatkan informasi yang cukup untuk mengerjakan operatornya, ia akan bergerak mundur, memanggil kembali kedua variabel dan operator tersebut untuk menyelesaikan aritmatikannya.

             Terkadang seseorang harus membedakan kapan sebuah operator dapat dikerjakan sesuai dengan tingkat atau derjatnya, hal yang sama juga berlaku dengan tanda kurung. Ketika ini terjadi atau ditemukan, ia harus mengerjakan operator dengan derajat yang lebih tinggi terlebih dahulu; kemudian bergerak mundur ke belakang untuk mengerjakan operator lainnya.

Bagaimana Manusia Menerjemahkan Operasi Infix ke Postfix?

            Ide dasarnya bukanlah untuk mengerjakan operasi infix, tetapi untuk menyusun ulang operator beserta variabelnya ke dalam format yang berbeda: notasi postfix. Notasi postfix yang sudah dihasilkan ini baru akan dikerjakan kemudian. Seperti sebelumnya, seorang manusia akan membaca operasi infix dari kiri ke kanan, melihat setiap karakter secara bergiliran. Sembari bergerak, ia akan menyalin setiap variabel dan operatornya ke dalam output postfix berupa string.

            Apabila karakter dalam string infix berupa variabel, maka ia akan langsung menyalinnya ke dalam string postfix. Ia akan langsung menyalin variabel ketika menemukannya, tidak peduli seberapa lama ia harus menunggu untuk menyalin operator yang berperan dalam variabel tersebut.

            Untuk dapat mengetahui kapan harus menyalin sebuah operator merupakan pekerjaaan yang lebih rumit, namun peraturannya sama dengan ketika mengerjakan operasi infix. Kapan saja seseorang dapat mulai mengerjakan operator dalam operasi infix, ia tidak akan langsung mengevaluasinya melainkan menyalinnya ke dalam string postfix.

            Sedangkan, untuk proses pengerjaan aritmatika, seorang manusia akan bergerak maju dan mundur mengikuti alur operasi infix untuk menyelesaikan terjemahannya ke dalam notasi postfic. Seseorang tidak dapat menuliskan operator ke dalam string output (postfix) apabila setelahnya diikuti dengan operator yang memiliki derajat lebih tinggi atau tanda kurung. Apabila ditemukan operator dengan derajat yang lebih tinggi, maka operator tersebut harus disalin terlebih dahulu.

Menyimpan Operator dalam Stack

        Penyimpanan operator pada postfix letaknya berbalik dengan penulisannya di operasi infix. Hal ini menunjukan bahwa sebuah stack mampu menjadi tempat yang baik untuk menyimpan operator-operator dalam sebuah ekspresi sembari seseorang menunggu untuk menggunakannya.

        Mengeluarkan (popping) sebuah benda dari stack memperbolehkan seseorang untuk bergerak mundur (kanan ke kiri) mengikuti alur inputan string. Seseorang tidak benar-benar memerika semua input string, melainkan hanya operator dan tanda kurung saja. Operator dan tanda kurung tersebut dimasukkan ke dalam stack ketika membaca input string, sehingga sekarang mereka dapat dipanggil dalam urutan yang terbalik melalui operasi popping pada stack.

        Untuk variabel (A,B, dan lain-lain) memiliki urutan yang sama pada ekspresi infix dan postfix, sehingga ini memungkinkan seseorang untuk langsung menuliskan variabel pada output ketika ditemukan pertama kali; variabel tidak perlu disimpan dalam stack.

Kode Pengimplementasian Stack untuk Mengubah Infix ke Postfix.

	import java.io.*;
	class StackX
	{
	private int maxSize;
	private char[] stackArray;
	private int top;
	//--------------------------------------
	public StackX(int s) //constructor
	{
	maxSize = s;
	stackArray = new char[maxSize];
	top = -1;
	}
	//-----------------------------------------
	public void push (char j) //put item on top of stack
	{stackArray[++top] = j;}
	//-----------------------------------------
	public char pop ()//take item from top of stack
	{return stackArray[top--];}
	//-----------------------------------------
	public char peek() //peek at top of stack
	{return stackArray[top];}
	//-----------------------------------------
	public boolean isEmpty() //true if stack is empty
	{return (top==-1);}
	//-----------------------------------------
	public int size() //return size
	{return top+1;}
	//-----------------------------------------
	public char peekN(int n) //return item at index n
	{return stackArray[n];}
	//-----------------------------------------
	public void displayStack(String s)
	{
	System.out.print(s);
	System.out.print("Stack (bottom-->top) : ");
	for(int j=0; j<size(); j++)
	{
	System.out.print(peekN(j));
	System.out.print(' ');
	}
	System.out.println("");
	}
	//-----------------------------------------
	}//end class StackX
	class InToPost //infix to postfix conversion
	{
	private StackX theStack;
	private String input;
	private String output = "";
	//-----------------------------------------
	public InToPost(String in) //constructor
	{
	input = in;
	int stackSize=input.length();
	theStack = new StackX(stackSize);
	}
	//-----------------------------------------
	public String doTrans() //do translation to postfic
	{
	for(int j=0; j<input.length(); j++)
	{
	char ch = input.charAt(j);
	theStack.displayStack("For "+ch +" "); //diagnostic
	switch(ch)
	{
	case'+': //it's + or -
	case'-':
	gotOper(ch,1); //go pop operators
	break; //(precedence 1)
	case'*': //it's * or /
	case'/':
	gotOper(ch,2); //go pop operators
	break; //(precedece 2)
	case'(': //left parentheses
	theStack.push(ch); //push it
	break;
	case ')' : //right parentheses
	gotParen(ch); //go pop operators
	break;
	default: //must be an operand
	output = output + ch; //write it to output
	break;
	}// end switch
	}//end for
	while(!theStack.isEmpty()) //pop remaining opers
	{
	theStack.displayStack("While "); //*diagnostic*
	output = output + theStack.pop(); //write to output
	}
	theStack.displayStack("End "); //*diagnostic*
	return output;
	}// end doTrans()
	public void gotOper(char opThis, int prec1)
	{ //got operator from input
	while(!theStack.isEmpty())
	{
	char opTop = theStack.pop();
	if(opTop== '(')
	{
	theStack.push(opTop); //restore '('
	break;
	}
	else //it's an operator
	{
	int prec2; //precendence of new op
	if(opTop =='+' || opTop=='-') //find new op prec
	prec2 =1;
	else
	prec2 = 2;
	if(prec2<prec1)
	{
	theStack.push(opTop); //save newly-popped op
	break;
	}
	else //prec of new not less
	output = output + opTop; //then prec of old
	} //end else (it's an operator)
	}//end while
	theStack.push(opThis); //push new operator
	} //end gotOp()
	//-----------------------------------------
	public void gotParen(char ch)
	{
	while(!theStack.isEmpty())
	{
	char chx = theStack.pop();
	if( chx == '(') //if popped '('
	break; //done
	else
	output = output + chx; //output it
	}//end while
	}//end popOps()
	//-----------------------------------------
	} // end class IntoPost
	public class infixApp
	{
	public static void main(String[] args) throws IOException
	{
	String input, output;
	while(true)
	{
	System.out.print("Enter infix: ");
	System.out.flush();
	input = getString(); //read a string
	if(input.equals("")) //quit if Enter
	break;
	InToPost theTrans = new InToPost(input);
	output = theTrans.doTrans(); //do translation
	System.out.println("Postfix is " + output + '\n');
	}//end while
	}//end main()
	//-----------------------------------------
	public static String getString() throws IOException
	{
	InputStreamReader isr = new InputStreamReader(System.in);
	BufferedReader br = new BufferedReader(isr);
	String s = br.readLine();
	return s;
	}
	} //end class InfixApp

view raw InfixtoPostfix.java hosted with ❤ by GitHub

        Fungsi main pada kelas InfixApp meminta pengguna untuk memasukan sebuah ekspresi infix. Input user kemudian dibaca oleh program melalui fungsi readString(). Program tersebut kemudian membuat sebuah objek InToPost yang mana diinisialisasi dengan nilai input string. Lalu, ia akan memanggil fungsi doTrans() agar objek tersebut dapat melakukan penerjemahan. Fungsi ini mengembalikan sebuah output postfix berupa string yang kemudian ditampilkan ke layar.

        Fungsi doTrans() menggunakan perintah switch untuk mengendalikan bermacam aturan penerjemahan seperti yang sudah disebutkan sebelumnya (derajat operator, variabel, dan lain-lain). Fungsi ini memanggil gotOper() ketika ia membaca sebuah operator dan memanggil goParen() ketika ia membaca tanda kurung.