Accepted Java Infix to Postfix based solution with explaination [600ms]


  • 27
    L

    The solution has 2 steps:

    1. parse the input string and convert it to postfix notation.
    2. evaluate the postfix string from step 1.

    Infix to postfix conversion

    converting a simple expression string that doesn't contain brackets to postfix is explained here. You can imagine the expression between brackets as a new simple expression (which we know how to convert to postfix). So when we encounter opening bracket "(" push it to the top stack. When we encounter a closing bracket ")" keep popping from stack until we find the matching "(", here we are removing all operators that belong to the expression between brackets. Then pop the "(" from the stack.

    One more thing to take into consideration, we don't want any operator to pop the "(" from the stack except the ")". We can handle this be assigning the "(" the lowest rank such that no operator can pop it.

    Evaluate postfix expression

    postfix evaluation is explained here

    If you have any ideas how to cut down the run time, please share your ideas :D.

    Disclaimer: I didn't write the included links, however I find them simple and neat.

    public class Solution {
    	int rank(char op){
    	    // the bigger the number, the higher the rank
    	    switch(op){
    	        case '+':return 1;
    	        case '-':return 1;
    	        case '*':return 2;
    	        case '/':return 2;
    	        default :return 0; // '(' 
    	    }
    	}
    	List<Object> infixToPostfix(String s) {
    		Stack<Character> operators = new Stack<Character>();
    		List<Object> postfix = new LinkedList<Object>();
    
    		int numberBuffer = 0;
    		boolean bufferingOperand = false;
    		for (char c : s.toCharArray()) {
    			if (c >= '0' && c <= '9') {
    				numberBuffer = numberBuffer * 10 + c - '0';
    				bufferingOperand = true;
    			} else {
    				if(bufferingOperand)
    					postfix.add(numberBuffer);
    				numberBuffer = 0;
    				bufferingOperand = false;
    				
    				if (c == ' '|| c == '\t')
    					continue;
    				
    				if (c == '(') {
    					operators.push('(');
    				} else if (c == ')') {
    					while (operators.peek() != '(')
    						postfix.add(operators.pop());
    					operators.pop(); // popping "("
    				} else { // operator
    					while (!operators.isEmpty() && rank(c) <= rank(operators.peek()))
    						postfix.add(operators.pop());
    					operators.push(c);
    				}
    			}
    
    		}
    		if (bufferingOperand)
    			postfix.add(numberBuffer);
    
    		while (!operators.isEmpty())
    			postfix.add(operators.pop());
    
    		return postfix;
    	}
    
    	int evaluatePostfix(List<Object> postfix) {
    		Stack<Integer> operands = new Stack<Integer>();
    		int a = 0, b = 0;
    		for (Object s : postfix) {
    			if(s instanceof Character){
    				char c = (Character) s;
    				b = operands.pop();
    				a = operands.pop();
    				switch (c) {
    					case '+': operands.push(a + b); break;
    					case '-': operands.push(a - b); break;
    					case '*': operands.push(a * b); break;
    					default : operands.push(a / b); 
    				}
    			}else { // instanceof Integer
    				operands.push((Integer)s);
    			}
    		}
    		return operands.pop();
    	}
    
    	public int calculate(String s) {
    		return evaluatePostfix(infixToPostfix(s));
    	}
    
    }
    

  • 0

    This "infix to postfix with postfix evaluation" solution is very cool! It's a general solution to calculator expression questions. With this solution, more operators can be handled easily, here is a variation of @leo_aly7 's solution:

    public class Solution {
        public int calculate(String s) {
            if (s == null || s.length() < 1) return Integer.MIN_VALUE;
            return evalSuffix(inToSuffix(s));
        }
        
        public int rank(Character op) {
            switch (op) {
                case '+': return 1;
                case '-': return 1;
                case '*': return 2;
                case '/': return 2;
                case '%': return 2;
                case '^': return 3; //you can add more operators
                default: return 0; //priority for '('
            }
        }
        
        public List<Object> inToSuffix(String s) {
            Stack<Character> opStack = new Stack<>();
            List<Object> suffix = new LinkedList<>();
            int num = 0;
            boolean numCached = false;
            char[] chars = s.toCharArray();
            for (char c : chars) {
                if (Character.isDigit(c)) {
                    num = num * 10 + (c - '0');
                    numCached = true;
                }
                else {
                    if (numCached) {
                        suffix.add(num);
                        num = 0;
                        numCached = false;
                    }
                    if (c == ' ' || c == '\t') continue;
                    if (c == '(') opStack.push('(');
                    else if (c == ')') {
                        while (opStack.peek() != '(') suffix.add(opStack.pop()); //op in () should be added first
                        opStack.pop();
                    }
                    else {
                        while (!opStack.isEmpty() && rank(c) <= rank(opStack.peek())) suffix.add(opStack.pop());
                        opStack.push(c);
                    }
                }
            }
            if (numCached) suffix.add(num);
            while (!opStack.isEmpty()) suffix.add(opStack.pop());
            return suffix;
        }
        
        public int evalSuffix(List<Object> suffix) {
            Stack<Integer> numStack = new Stack<>();
            int num1 = 0;
            int num2 = 0;
            for (Object o : suffix) {
                if (o instanceof Character) {
                    char op = (Character)o;
                    num2 = numStack.pop();
                    num1 = numStack.pop();
                    switch (op) {
                        case '+': numStack.push(num1 + num2); break;
                        case '-': numStack.push(num1 - num2); break;
                        case '*': numStack.push(num1 * num2); break;
                        case '/': numStack.push(num1 / num2); break;
                        case '%': numStack.push(num1 % num2); break;
                        case '^': numStack.push((int)Math.pow((double)num1, (double)num2)); break;
                    }
                }
                else numStack.push((Integer)o);
            }
            return numStack.pop();
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.