Infix to Postfix and Prefix conversion

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

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*.

MCQ #14

Question : 

There are two code snippets given below. You have to predict output for both.

First :

String str1="str";
String str2="ing";
String concat=str1+str2;

System.out.println(concat=="string");

Second :

final String str1="str";
final String str2="ing";
String concat=str1+str2;

System.out.println(concat=="string");

In both case answer will be either true or false.

Answer : 

Answer is 1st case is false.

Answer in 2nd case is true.

Explanation :

When Java code is compiled, compiler does some optimizations of it's own. An expression that is know to not change during runtime is know as compile time constant expression. So lets say if you have a String
String concat = "str" + "ing";
after compilation it becomes
String concat = "string";
So if question is framed like how many String instances are created in above java code then the answer is one. String literals are interned. So lets come to our problem

1. (False)In first case Strings are not final. Also as we know String is immutable in nature. Concatenation of two String literals yields a new String instance and hence the answer on comparison would be false.
2. (True)In second case Strings are defined as final. That equivalently means the Strings will not change at runtime and hence they form compile time constant expression. So when the code is compiled concat actually points to "string" literal(which is interned as all String literals are). Now since we are comparing this with another String literal with same content both will point to same String instance in the String pool. So the answer in this case would be true.   

Important Links

1. Difference between using == operator and equals() method in Java
2. Comparing strings with == which are declared final in Java
3. how many java String objects will be created in the statement String s=“abc”+“xyz”