Infix to PostFix Conversion using Stacks
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);
}
}
}
Subscribe to:
Post Comments
(
Atom
)
No comments :
Post a Comment