Question :
Question is simply to covert a given infix expression to both prefix as well as postfix notation. The postfix part of the question is picked up from the code chef question --> Transform the Expression . I have simply extended it to output prefix part as well.
Code :
package CodeChef;
import java.util.Stack;
/**
* Created by Aniket on 2/23/14.
*/
public class PostFixConverter {
public static void main(String args[]){
String infix = "((a+b)*(z+x))";
System.out.println("Postfix : " + printPostFix(infix));
System.out.println("Prefix : " + printPreFix(infix));
}
public static String printPostFix(String str){
Stack stack = new Stack();
String postfix = "";
for(int i=0;i<str.length();i++){
char c = str.charAt(i);
if(Character.isLetter(c)){
postfix = postfix + c;
}
else if(c == '('){
continue;
}
else if(c == ')'){
postfix = postfix + ((Character)stack.pop()).toString();
}
else{
stack.push(c);
}
}
return postfix;
}
public static String printPreFix(String str){
Stack stack = new Stack();
String prefix = "";
for(int i=str.length()-1;i>=0;i--){
char c = str.charAt(i);
if(Character.isLetter(c)){
prefix = ((Character)c).toString() + prefix;
}
else if(c == '('){
prefix = ((Character)stack.pop()).toString() + prefix;
}
else if(c == ')'){
continue;
}
else{
stack.push(c);
}
}
return prefix;
}
}
Output :
Postfix : ab+zx+*
Prefix : *+ab+zx
Prefix : *+ab+zx
Note :
Note that the expression provided as input is well bracketed input and hence we are not taking care of ordering. If the question asks for ordering then you need to take care of that as well. For example if infix expression in a+b*c answer(post fix) would be abc*+ and not ab+c*.
, so in that case, Quicksort takes O(n²) time.
