Thursday, November 6, 2014

Facebook: Expression Evaluation

Write a function that calculates input strings with operators +,-,*,/ eg. "5+5*6" should output 35

Question to ask the interviewer:
1. Can we assume that the input is valid?
2. Do we need to consider the parenthesis, i.e, precedence?

If consider the parenthesis is existed in the input:
Idea: Use two stacks
1. Operator stack, store the operators
2. Value stack, store the integers.

1. While the input tokens are reached to the end
  -- If the token is a number, push it to the value stack
  -- If the token is a left parenthesis, push ito to the operator stack.
  -- If the token is a right parentheis, pop the operator stack until the top of the stack is a left parenthesis
     Then pop two numbers from the value stack and one operator from the operator stack, calculate the results and
     push it into the value stack again
     pop out the left parenthesis and discard it.
     
  -- If the token is a operator, evaluate if top of the operator stack has equal or higher precedence. If yes, do the calculatation first
      then add the current operator into the operator stack.

2. While the operator stack is not empty
    -- Do calcuations until the operator stack is empty
    
3. Pop out the last number in the value stack, which is the final result.

Code (Java):

public class Solution {
    public int infixNotation(String[] tokens) {
        if (tokens == null || tokens.length  == 0) {
            return 0;
        }
        
        Stack<String> op = new Stack<String>();
        Stack<Integer> value = new Stack<Integer>();
        
        for (String token : tokens) {
            if (isNumber(token)) {
                value.push(Integer.valueOf(token));
            } else if (token.equals("(")) {
                op.push(token);
            } else if (token.equals(")")) {
                while (!op.peek().equals("(")) {
                    String operator = op.pop();
                    int oprand2 = value.pop();
                    int oprand1 = value.pop();
                    
                    int result = calculate(operator, oprand1, oprand2);
                    value.push(result);
                }
                
                op.pop(); // discard the left parenthesis
            } else if (isOperator(token)) {
                while (!op.isEmpty() && hasHigherPrecendence(token, op.peek())) {
                    int oprand2 = value.pop();
                    int oprand1 = value.pop();
                    String operator = op.pop(); 
                    
                    int result = calculate(operator, oprand1, oprand2);
                    value.push(result);
                }
                
                op.push(token);
            }
        }
        
        while (!op.isEmpty()) {
            String operator = op.pop();
            int oprand2 = value.pop();
            int oprand1 = value.pop();
            
            int result = calculate(operator, oprand1, oprand2);
            value.push(result);
        }
        
        return value.pop();
    }
    
    private boolean isNumber(String str) {
        return str.charAt(0) >= '0' && str.charAt(0) <= '9';
    }
    
    private boolean isOperator(String str) {
        return str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/");
    }
    
    int calculate(String operator, int oprand1, int oprand2) {
        int result = 0;
        
        switch(operator) {
            case "+" : result = oprand1 + oprand2;
            break;
            
            case "-" : result = oprand1 - oprand2;
            break;
            
            case "*" : result = oprand1 * oprand2;
            break;
            
            case "/" : result = oprand1 / oprand2;
            break;
        }
        
        return result;
    }
    
    boolean hasHigherPrecendence(String op1, String op2) {        
        
        if (op2.equals("(")) {
            return false;
        }
        
        if ((op1.equals("*") || op1.equals("/")) && (op2.equals("+") || op2.equals("-"))) {
            return false;
        } else {
            return true;
        }
    }
    
    public static void main(String[] args) {
      Solution sol = new Solution();
      
      String[] tokens = new String[]{"100", "*", "(", "2", "+", "12", ")", "/", "14"};

      int result = sol.infixNotation(tokens);
      
      System.out.println("Result is " + result);
    }

}


If not consider the parenthesis in the input tokens:
If we don't consider the left and right parenthesis, we could still use the code above, but the logic could be simpler:
1. If the token is a number, push into the number stack
2. If the token is a operator, peek the top of the operator stack. If the top of the operator stack has higher precedence, do the calculation first before we push the current operator. 

3. After we iterate all the tokens, check the operator stack. If the operator stack is not empty, do the calculations until the operator stack becomes empty.

4. Pop out the last number in the value stack, which is the final result.

Code (Java):
import java.util.*;
public class Solution {
    public int infixNotation(String[] tokens) {
        if (tokens == null || tokens.length == 0) {
            return 0;
        }
        
        Stack<Integer> numStack = new Stack<Integer>();
        Stack<String> opStack = new Stack<String>();
        
        int i = 0;
        while (i < tokens.length) {
            String token = tokens[i];
            if (isNumber(token)) {
                numStack.push(Integer.valueOf(token));
                i++;
            } else {  // operator
                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(String str) {
        return str.charAt(0) >= '0' && str.charAt(0) <= '9';
    }
    
    private void calculate(Stack<Integer> numStack, Stack<String> opStack) {
        int operands2 = numStack.pop();
        int operands1 = numStack.pop();
        
        String operator = opStack.pop();
        
        int result = 0;
        
        switch (operator) {
            case "+" : result = operands1 + operands2;
            break;
            
            case "-" : result = operands1 - operands2;
            break;
            
            case "*" : result = operands1 * operands2;
            break;
            
            case "/" : result = operands1 / operands2;
            break;
        }
        
        numStack.push(result);
    }
    
    private boolean hasHigherPrecedence(String str1, String str2) {
        if (str1.equals("*") || str1.equals("/")) {
            return true;
        }
        
        if ((str1.equals("+") || str1.equals("-")) && (str2.equals("+") || str2.equals("-"))) {
            return true;
        }
        
        return false;
    }

    public static void main(String[] args) {
      Solution sol = new Solution();

      String[] tokens = new String[]{"3", "/", "5", "-", "3"};
      System.out.println(sol.infixNotation(tokens));
    }
}


Update on 12/3/14:

import java.util.*;
public class Solution {
    public int infixNotation(String[] tokens) {
        if (tokens == null || tokens.length == 0) {
            return 0;
        }
        
        Stack<Integer> numStack = new Stack<Integer>();
        Stack<String> opStack = new Stack<String>();
        
        for (String token : tokens) {
            if (isOperator(token)) {
                if (opStack.isEmpty()) {
                    opStack.push(token);
                } else if (hasHigherPrecedence(opStack.peek(), token)) {
                    calculates(opStack, numStack);
                    opStack.push(token);
                } else {
                    opStack.push(token);
                    calculates(opStack, numStack);
                }
            } else {
                numStack.push(Integer.valueOf(token));
            }
        }
        
        while (!opStack.isEmpty()) {
            calculates(opStack, numStack);
        }
        
        return numStack.pop();
    }
    
    private boolean isOperator(String str) {
        return str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/");
    }
    
    // Check if str a has higher or equal precedence than b
    private boolean hasHigherPrecedence(String a, String b) {
        if (a.equals("*") || a.equals("/")) {
            return true;
        }
        
        if ((a.equals("+") || a.equals("-")) && (b.equals("+") || b.equals("-"))) {
            return true;
        }
        
        return false;
    }
    
    private void calculates(Stack<String> opStack, Stack<Integer> numStack) {
        String op = opStack.pop();
        int oprand2 = numStack.pop();
        int oprand1 = numStack.pop();
        
        int result = 0;
        
        switch (op) {
            case "+" : result = oprand1 + oprand2;
            break;
            
            case "-" : result = oprand1 - oprand2;
            break;
            
            case "*" : result = oprand1 * oprand2;
            break;
            
            case "/" : result = oprand1 / oprand2;
            break;
        }

        numStack.push(result);
        
    }

    public static void main(String[] args) {
      Solution sol = new Solution();

      String[] tokens = new String[]{"3", "*", "5", "*", "3"};
      System.out.println(sol.infixNotation(tokens));
    }
}

Constant space solution:
If we don't consider the parenthesis in the input string, we may come out a constant space solution without using a stack.

Code (Java):
public static int eval(String[] tokens) {
    int sum = 0;
    int m = 1;
    boolean divide = false;
    for (int i = 0; i < tokens.length; i++) {
        if (i % 2 == 0) {
            int digit = (new Integer(tokens[i])).intValue();
            if (!divide) {
                m *= digit;
            } else {
                m /= digit;
            }
        } else {
            String op = tokens[i];
            divide = false;
            if (op.equals("+")) {
                sum += m;
                m = 1;
            } else if (op.equals("-")) {
                sum += m;
                m = -1;
            } else if (op.equals("/")) {
                divide = true;
            }
        }
    }
    sum += m;
    return sum;
}


No comments:

Post a Comment