Wednesday, September 2, 2015

Leetcode: Basic Calculator II

Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +-*/ operators and empty spaces . The integer division should truncate toward zero.
You may assume that the given expression is always valid.
Some examples:
"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5
Note: Do not use the eval built-in library function.
Code (Java):
public class Solution {
    public int calculate(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        String delim = "[ ]+";
        s = s.replaceAll(delim, "");
        
        Stack<Integer> numStack = new Stack<Integer>();
        Stack<Character> opStack = new Stack<Character>();
        
        int result = 0;
        
        int i = 0;
        while (i < s.length()) {
            char token = s.charAt(i);
            if (isNumber(token)) {
                StringBuffer sb = new StringBuffer();
                while (i < s.length() && isNumber(s.charAt(i))) {
                    sb.append(s.charAt(i));
                    i++;
                }
                
                int val = Integer.valueOf(sb.toString());
                numStack.push(val);
            } else {
                if (opStack.isEmpty() || !hasHigherPrecedence(opStack.peek(), token)) {
                    opStack.push(token);
                    i++;
                } else {
                   calculate(numStack, opStack);
                }
            }
        }
        
        while(!opStack.isEmpty()) {
            calculate(numStack, opStack);
        }
        
        return numStack.pop();
    }
    
    private boolean isNumber(char character) {
        return character >= '0' && character <= '9';
    }
    
    private void calculate(Stack<Integer> numStack, Stack<Character> opStack) {
        int num2 = numStack.pop();
        int num1 = numStack.pop();
        char oprator = opStack.pop();
        
        int result = 0;
        
        switch(oprator) {
            case '+' : result = num1 + num2;
            break;
            
            case '-' : result = num1 - num2;
            break;
            
            case '*' : result = num1 * num2;
            break;
            
            case '/' : result = num1 / num2;
            break;
        }
        
        numStack.push(result);
    }
    
    private boolean hasHigherPrecedence(char str1, char str2) {
        if (str1 == '*'|| str1 == '/') {
            return true;
        }
        
        if ((str1 == '+' || str1 == '-') && (str2 == '+' || str2 == '-')) {
            return true;
        }
        
        return false;
    }
}

1 comment:

  1. If you need your ex-girlfriend or ex-boyfriend to come crawling back to you on their knees (even if they're dating somebody else now) you got to watch this video
    right away...

    (VIDEO) Have your ex CRAWLING back to you...?

    ReplyDelete