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>