Sunday, November 1, 2015

Zenefits: Infix expression

Infix expression.

这题有点像Leetocde basic calculator 那题。 

http://buttercola.blogspot.com/2015/08/leetcode-basic-calculator.html


Understand the problem:
The problem looks complicated to implement, actually could be memorized in a template way. 
If the token is a number, then push it to the num stack. 
If the token is a operator, there are 5 cases to consider:
1. If the opStack is empty
  -- push into opStack
2. If the token is + or -
  -- Check the top of the opStack. 
     -- If the top is '(', then push the token into opStack.
     -- Else (which means has higher or equal precedence), consume the stack by doing one computation. 
3. If the token is * or /
     -- If the top is '(', push the token into opStack
     -- Else if top has lower precedence ( + or -), push the token into opStack.
     -- Else if the top has equal precedence (* or /), consume the stack by doing one computation. 
4. If the token is (
    -- Push into opStack
5. If the token is )
   -- Doing computations until we see the '(' in the opStack. 


Code (Java):
import java.util.*;
public class Solution {
    public int calculate(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
         
        // parse the string
        String delim = "\\s+";
        s = s.replaceAll("\\s+", "");
 
        Stack<Integer> numStack = new Stack<Integer>();
        Stack<Character> opStack = new Stack<Character>();
         
        for (int i = 0; i < s.length(); i++) {
            char elem = s.charAt(i);
            if (Character.isDigit(elem)) {
                // To number
                int num = elem - '0';
                int j = i + 1;
                 
                while (j < s.length() && Character.isDigit(s.charAt(j))) {
                    num = num * 10 + (s.charAt(j) - '0');
                    j++;
                }
                numStack.push(num);
                i = j - 1;
            } else { // Operator
                if (opStack.isEmpty()) {
                    opStack.push(elem);
                } else if (elem == '*' || elem == '/') {
                    char top = opStack.peek();
                    if (top == '(') {
                        opStack.push(elem);
                    } else if (top == '+' || top == '-') {
                        opStack.push(elem);
                    } else {
                        compute(numStack, opStack);
                        opStack.push(elem);
                    }
                } else if (elem == '+' || elem == '-') {
                    char top = opStack.peek();
                    if (top == '(') {
                        opStack.push(elem);
                    } else {
                        compute(numStack, opStack);
                        opStack.push(elem);
                    }
                } else if (elem == '(') {
                    opStack.push(elem);
                } else if (elem == ')') { // Right ")"
                    while ((!opStack.isEmpty()) && (opStack.peek() != '(')) {
                        compute(numStack, opStack);
                    }
                    opStack.pop();
                }
            }
        }
         
        while (!opStack.isEmpty()) {
            compute(numStack, opStack);
        }
         
        return numStack.pop();
    }
     
    private void compute(Stack<Integer> numStack, Stack<Character> opStack) {
         
        if (numStack.size() < 2) {
            while (!opStack.isEmpty()) {
                opStack.pop();
            }
            return;
        }
         
        int num2 = numStack.pop();
        int num1 = numStack.pop();
         
        char op = opStack.pop();
        int ans = 0;
         
        switch(op) {
            case '+': ans = num1 + num2;
            break;
             
            case '-': ans = num1 - num2;
            break;
             
            case '*': ans = num1 * num2;
            break;
             
            case '/': ans = num1 / num2;
            break;
        }
         
        numStack.push(ans);
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        String input = sc.nextLine();
        
        Solution solution = new Solution();
        
        int result = solution.calculate(input);
        
        System.out.println(result);
    }
}

Summary:
Be careful the different between Scanner.next() and Scanner.nextLine(). next() returns the next complete token in String, where the nextLine returns the next line terminated by a return. 

No comments:

Post a Comment