Convert infix expression to prefix expression
class StackX{
private int maxSize;
private char[] stackArray;
private int top;
public StackX(int s){
maxSize=s;
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);
}
public int size(){
return top+1;
}
public char 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("");
}
}
class InToPost{
private StackX theStack;
private String input;
private String output="";
public InToPost(String in){
input=in;
int stackSize=input.length();
theStack=new StackX(stackSize);
}
public void gotOper(char opThis,int prec1){//priority
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(ch=='(')
break;
else
output+=chx;
}
}
public String doTrans(){
for(int j=0;j<input.length();j++){
char ch=input.charAt(j);
theStack.displayStack("for "+ch+" ");
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+=ch;
break;
}
}
while(!theStack.isEmpty()){
theStack.displayStack("while ");
output+=theStack.pop();
}
theStack.displayStack("end ");
return output;
}
}
public class infix {
public static void main(String[] args) throws IOException{
String input,output;
while(true){
System.out.print("enter infix:");
System.out.flush();
input=getString();
if(input.equals(""))
break;
InToPost theTrans=new InToPost(input);
output=theTrans.doTrans();
System.out.println("postfix is "+output+'\n');
}
}
private static String getString() throws IOException {
InputStreamReader isr=new InputStreamReader(System.in);
BufferedReader br=new BufferedReader(isr);
String s=br.readLine();
return s;
}
}