Java/Collections Data Structure/Infix Postfix

Converts infix arithmetic expressions to postfix

   <source lang="java">

import java.io.IOException; public class InToPost {

 private Stack theStack;
 private String input;
 private String output = "";
 public InToPost(String in) {
   input = in;
   int stackSize = input.length();
   theStack = new Stack(stackSize);
 }
 public String doTrans() {
   for (int j = 0; j < input.length(); j++) {
     char ch = input.charAt(j);
     switch (ch) {
     case "+": 
     case "-":
       gotOper(ch, 1); 
       break; //   (precedence 1)
     case "*": // it"s * or /
     case "/":
       gotOper(ch, 2); // go pop operators
       break; //   (precedence 2)
     case "(": // it"s a left paren
       theStack.push(ch); // push it
       break;
     case ")": // it"s a right paren
       gotParen(ch); // go pop operators
       break;
     default: // must be an operand
       output = output + ch; // write it to output
       break;
     }
   }
   while (!theStack.isEmpty()) {
     output = output + theStack.pop();
   }
   System.out.println(output);
   return output; // return postfix
 }
 public void gotOper(char opThis, int prec1) {
   while (!theStack.isEmpty()) {
     char opTop = theStack.pop();
     if (opTop == "(") {
       theStack.push(opTop);
       break;
     }// it"s an operator
     else {// precedence of new op
       int prec2;
       if (opTop == "+" || opTop == "-")
         prec2 = 1;
       else
         prec2 = 2;
       if (prec2 < prec1) // if prec of new op less
       { //    than prec of old
         theStack.push(opTop); // save newly-popped op
         break;
       } else
         // prec of new not less
         output = output + opTop; // than prec of old
     }
   }
   theStack.push(opThis);
 }
 public void gotParen(char ch){ 
   while (!theStack.isEmpty()) {
     char chx = theStack.pop();
     if (chx == "(") 
       break; 
     else
       output = output + chx; 
   }
 }
 public static void main(String[] args) throws IOException {
   String input = "1+2*4/5-7+3/6";
   String output;
   InToPost theTrans = new InToPost(input);
   output = theTrans.doTrans(); 
   System.out.println("Postfix is " + output + "\n");
 }
 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);
   }
 }

}

      </source>
   
  
 
  

Parse postfix arithmetic expressions

   <source lang="java">

import java.io.IOException; public class ParsePost {

 private Stack theStack;
 private String input;
 public ParsePost(String s) {
   input = s;
 }
 public int doParse() {
   theStack = new Stack(20);
   char ch;
   int j;
   int num1, num2, interAns;
   for (j = 0; j < input.length(); j++) {
     ch = input.charAt(j); 
     theStack.displayStack("" + ch + " ");
     if (ch >= "0" && ch <= "9") // if a number push it
       theStack.push((int) (ch - "0"));   
     else // it"s an operator
     {
       num2 = theStack.pop();
       num1 = theStack.pop();
       switch (ch) {
       case "+":
         interAns = num1 + num2;
         break;
       case "-":
         interAns = num1 - num2;
         break;
       case "*":
         interAns = num1 * num2;
         break;
       case "/":
         interAns = num1 / num2;
         break;
       default:
         interAns = 0;
       }
       theStack.push(interAns);
     }
   }
   interAns = theStack.pop();
   return interAns;
 }
 public static void main(String[] args) throws IOException {
   String input = "1-2+3*4+5/6-7+8*9";
   int output;
   ParsePost aParser = new ParsePost(input);
   output = aParser.doParse();
   System.out.println("Evaluates to " + output);
 }
 class Stack {
   private int maxSize;
 
   private int[] stackArray;
 
   private int top;
 
   public Stack(int size) {
     maxSize = size;
     stackArray = new int[maxSize];
     top = -1;
   }
 
   public void push(int j) {
     stackArray[++top] = j;
   }
 
   public int pop() {
     return stackArray[top--];
   }
 
   public int peek() {
     return stackArray[top];
   }
 
   public boolean isEmpty() {
     return (top == -1);
   }
 
   public boolean isFull() {
     return (top == maxSize - 1);
   }
 
   public int size() {
     return top + 1;
   }
 
   public int peekN(int 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("");
   }
 }

}

      </source>