Java Infix Expression To Postfix Expression

Chapter: Data Structures Last Updated: 25-10-2016 18:11:14 UTC

Program:

            /* ............... START ............... */
                
import java.io.IOException;

public class JavaInfixExpressionToPostfixExpression {

	private Stack theStack;
	private String input;
	private String output = "";

	public JavaInfixExpressionToPostfixExpression(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;
			case '*':
			case '/':
				gotOper(ch, 2);
				break;
			case '(':
				theStack.push(ch);
				break;
			case ')':
				gotParen(ch);
				break;
			default:
				output = output + ch;
				break;
			}
		}
		while (!theStack.isEmpty()) {
			output = output + theStack.pop();
		}
		System.out.println(output);
		return output;
	}

	public void gotOper(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 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;
		JavaInfixExpressionToPostfixExpression theTrans = 
				new JavaInfixExpressionToPostfixExpression(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);
		}
	}
}

                /* ............... END ............... */
        

Output

124*5/+7-36/+
Postfix is 124*5/+7-36/+

Tags

Infix Expression To Postfix Expression, Java, Data Structures

Similar Programs Chapter Last Updated
HashMap Implementation In Java Data Structures 07-07-2018
Linked List Implementation In Java Data Structures 09-03-2018
Queue Implementation In Java Data Structures 22-09-2018
Stack Implementation In Java Data Structures 22-09-2018
Binary Search Tree Java Data Structures 11-02-2018
Insertion Sort In Java Data Structures 10-02-2018
Java Stack Example Data Structures 16-10-2017
Java String Array Sort Data Structures 31-03-2017
Java Hashmap Add Key And Value Data Structures 25-03-2017
Java Binary Tree Vertical Sum Data Structures 11-11-2016
Java Binary Tree Boundary Traversal Data Structures 11-11-2016
Java Binary Tree Lowest Common Ancestor (LCA) Data Structures 11-11-2016
Java Binary Tree Maximum Element Data Structures 11-11-2016
Java Three Dimensional Array Data Structures 28-10-2016
Java Linked List Add Element First And Last Data Structures 24-10-2016
Java Maximum Element From Vector Data Structures 24-10-2016
Java Binary Search On Vector Data Structures 24-10-2016
Java Get Elements Of LinkedList Data Structures 23-10-2016
Java Linked List Update Element Data Structures 23-10-2016
Java Delete Elements From LinkedList Data Structures 23-10-2016
Java Double Ended Queue Data Structures 09-10-2016
Java Dynamic Queue Using Array Data Structures 26-09-2018
Java Queue Array Based Implementation Data Structures 07-10-2016
Java Sort Short Array Data Structures 25-09-2016
Java Sort Long Array Data Structures 25-09-2016
Java Sort Int Array Data Structures 19-09-2016
Java Sort Float Array Data Structures 19-09-2016
Java Sort Double Array Data Structures 19-09-2016
Java Sort Char Array Data Structures 19-09-2016
Java Sort Byte Array Data Structures 19-09-2016

1 2 3