Ubah Ekspresi Infiks Menjadi Notasi Postfix

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).

Postfix adalah metode penulisan dengan menuliskan operator setelah operand dan tanpa menuliskan tanda kurung.
Salah satu contoh proses pengubahan infix menjadi postfix dari karakter:
( A + B ) / (( C – D ) * E ^ F)

 

1. Main

DATA HOSTED WITH ♥ BY PASTEBIN.COM - DOWNLOAD RAW - SEE ORIGINAL

1. import java.io.BufferedReader;
2. import java.io.IOException;
3. import java.io.InputStreamReader;
4.  
5. class Main {
6.  
7.    public static void main(String[] args) throws IOException{
8.      String input, output;
9.      while(true){
10.         System.out.print("Enter infix: ");
11.         System.out.flush();
12.         input = getString();
13.         if( input.equals(""))
14.            break;
15.  
16.         ToPostfix theTrans = new ToPostfix(input);
17.         output = theTrans.trabslation();
18.            System.out.println("Postfix is " + output + '\\n');
19.      }
20. }
21.  
22.  
23. public static String getString() throws IOException{
24.     InputStreamReader isr = new InputStreamReader(System.in);
25.     BufferedReader br = new BufferedReader(isr);
26.     String s = br.readLine();
27.     return s;
28.    }
29. }

2. Queue

DATA HOSTED WITH ♥ BY PASTEBIN.COM - DOWNLOAD RAW - SEE ORIGINAL

1. public class Queue {
2.    private int size;
3.    char queueArr[];
4.    int front;
5.    int rear;
6.    int currentSize = 0;
7.  
8.    public Queue(int size) {
9.      this.size = size;
10.      front = 0;
11.      rear = -1;
12.      queueArr = new char[this.size];
13.   }
14.  
15.    public void enqueue(char data) {
16.    if (!isFull()){
17.      rear++;
18.    if (rear == size) {
19.      rear = 0;
20.   }
21.      queueArr[rear] = data;
22.      currentSize++;
23.   }
24. }
25.   public char dequeue() {
26.   char fr = 0;
27.   if (!isEmpty()){
28.     fr = queueArr[front];
29.      front++;
30.   if (front == size) {
31.      front = 0;
32.  }
33.     currentSize--;
34.      return fr;
35.  }
36. return fr;
37. }
38.  
39.    public boolean isFull() {
40.    if (currentSize == size) {
41.     return true;
42.   }
43. return false;
44. }
45.  
46.    public boolean isEmpty() {
47.    if (currentSize == 0) {
48.     return true;
49.  }
50.   return false;
51. }
52.  
53.   public String getString(){
54.   String str = "";
55.   while(!isEmpty()){
56.      str = str + dequeue();
57.  }
58.    return str;
59.     }
60. }

3. Stack

DATA HOSTED WITH ♥ BY PASTEBIN.COM - DOWNLOAD RAW - SEE ORIGINAL

1. class Stack
2. {
3.    private int maxSize;
4.    private char[] stackArray;
5.    private int top;
6.  
7.    public Stack(int s){
8.      maxSize = s;
9.      stackArray = new char[maxSize];
10.      top = -1;
11.   }
12.  
13.    public void push(char j){
14.       stackArray[++top] = j;
15.   }
16.    public char pop(){
17.      return stackArray[top--];
18.   }
19.   public char peek(){
20.     return stackArray[top];
21.   }
22.   public boolean isEmpty(){
23.     return (top == -1);
24.   }
25.  public int size(){
26.    return top+1;
27.   }
28.  
29.  
30.   public char peekN(int n){
31.    return stackArray[n];
32.   }
33. }

4. ToPostfix

DATA HOSTED WITH ♥ BY PASTEBIN.COM - DOWNLOAD RAW - SEE ORIGINAL

1. class ToPostfix{
2.    private Stack theStack;
3.    private String input;
4.    private Queue queue;
5.  
6.    public ToPostfix(String in){
7.      input = in;
8.      int stackSize = input.length();
9.      int queueSize = input.length();
10.      queue = new Queue(queueSize);
11.      theStack = new Stack(stackSize);
12.   }
13.    public String trabslation(){
14.      for(int j=0; j<input.length(); j++){
15.        char ch = input.charAt(j);
16.        switch(ch){
17.          case '+':
18.          case '-':
19.          operand(ch, 1);
20.          break;
21.  
22.          case '*':
23.          case '/':
24.          operand(ch, 2);
25.          break;
26.  
27.          case '(':
28.          theStack.push(ch);
29.          break;
30.  
31.          case ')':
32.          parent(ch);
33.          break;
34.  
35.          default:
36.          queue.enqueue(ch);
37.          break;
38.      }
39. }
40.  
41.      while( !theStack.isEmpty()){
42.         queue.enqueue(theStack.pop());
43.     }
44.         return queue.getString();
45. }
46.     public void operand(char opThis, int prec1){
47.     while( !theStack.isEmpty()){
48.     char opTop = theStack.pop();
49.     if( opTop == '(' ){
50.        theStack.push(opTop);
51.     break;
52. }
53.      else{
54.      int prec2;
55.      if(opTop=='+' || opTop=='-')
56.         prec2 = 1;
57.      else
58.          prec2 = 2;
59.       if(prec2 < prec1){
60.           theStack.push(opTop);
61.           break;
62.   }
63.       else
64.          queue.enqueue(opTop);
65.     }
66. }
67. theStack.push(opThis);
68. }
69.     public void parent(char ch){
70.     while( !theStack.isEmpty()){
71.     char chx = theStack.pop();
72.      if( chx == '(' )
73.         break;
74.      else
75.         queue.enqueue(chx);
76.       }
77.     }
78.  }

Output