A Way For Learning

Infix to PostFix Conversion using Stacks

No comments
Write a program to convert infix notation to postfix notation using stack.
----------------------------Program-------------------------------------

public class InfixToPostfix {
   private Stack theStack;
   private String infix;
   private String output = "";
   public InfixToPostfix(String infix) {
    this.infix= infix;
      int stackSize = infix.length();
      theStack = new Stack(stackSize);
   }
   public String convertToPostfix() {
      for (int j = 0; j < infix.length(); j++) {
         char ch = infix.charAt(j);
         switch (ch) {
            case '+': 
            case '-':
             gotOperator(ch, 1); 
            break; 
            case '*': 
            case '/':
             gotOperator(ch, 2); 
            break; 
            case '(': 
             theStack.push(ch);
            break;
            case ')': 
             gotParenthesis(ch); 
            break;
            default: 
             output = output + ch; 
            break;
         }
      }
      while (!theStack.isEmpty()) {
         output = output + theStack.pop();
      }
      return output; 
   }
   public void gotOperator(char opThis, int prec1) {
      while (!theStack.isEmpty()) {
         char opTop = theStack.pop();
         if (opTop == '(') {
            theStack.push(opTop);
            break;
         }
         else {
            int prec2;
            if (opTop == '+' || opTop == '-')
            prec2 = 1;
            else
            prec2 = 2;
            if (prec2 < prec1) { 
               theStack.push(opTop);
               break;
            }
      else
            output = output + opTop;
         }
      }
      theStack.push(opThis);
   }
   public void gotParenthesis(char ch){ 
      while (!theStack.isEmpty()) {
         char chx = theStack.pop();
         if (chx == '(') 
         break; 
         else
         output = output + chx; 
      }
   }
   
   class Stack {
      private int maxSize;
      private char[] stackArray;
      private int top;
      public Stack(int max) {
         maxSize = max;
         stackArray = new char[maxSize];
         top = -1;
      }
      public void push(char j) {
         stackArray[++top] = j;
      }
      public char pop() {
         return stackArray[top--];
      }
      public char peek() {
         return stackArray[top];
      }
      public boolean isEmpty() {
         return (top == -1);
     }
   }
}

No comments :

Post a Comment