Infix to postfix conversion of regular expression | Set 1


import java.util.Stack;

class InfixToPostfix {
    static String toPostfix(String infix) {
        // stack to store operators 
        Stack stack = new Stack<>();
        StringBuilder result = new StringBuilder(); // store final result
        int i = 0;
        while(i < infix.length()) {
            char ch = infix.charAt(i);
            if(isOperand(ch)) {
                // if it's operand then add into result 
                result.append(ch);
                i++;
            } else {
                // deal with operator 
                if(stack.empty() || getPrecedence(ch) > getPrecedence(stack.peek())) {
                    // precendence of input operator is greater than operator 
                    // at stack top then add input operator to stack 
                    stack.push(ch);
                    i++;
                } else {
                    // precendence of input operator is <= precendence of stack top 
                    // operator so pop stack and add into result
                    result.append(stack.pop());
                }
            }
        }
        // pop out whatever is left in stack and insert into result 
        while(!stack.empty()) {
            result.append(stack.pop());
        }
        return result.toString();
    }
    private static boolean isOperand(char ch) {
        switch(ch){
            case '+':
            case '-':
            case '*':
            case '/':
                return false;
        }
        return true;
    }
    private static int getPrecedence(char ch) {
        switch(ch){
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
                return 2;
        }
        return 0;
    }
	public static void main (String[] args) {
		String infix = "a+b*c-d/e";
		System.out.println("Infix : " + infix + ", Postfix : " + toPostfix(infix));
	}
}


Output
         Infix : a+b*c-d/e, Postfix : abc*+de/- 

Comments

Popular posts from this blog

SQL basic interview question

gsutil Vs Storage Transfer Service Vs Transfer Appliance