Monday, November 2, 2015

Zenefits: Reverse polish notation

有点像 reverse polish notation 的变种,计算一个表达式的值的。要求自行设计表达式的数据结构并计算表达式的值。
有几种特殊情况
1. 单输入一个数,比如 [0],是合法,结果为0;. From 1point 3acres bbs
2. 单输入一个运算符也是合法的。 无数字运算的 ‘+’, ‘-‘, ‘/’ 结果为 0, 单个 ‘*’ 的结果为 1.
3. 一个运算符可以有好几个计算数字。 比如输入为 [‘+’, 1, 2, 3],结果为1 + 2 + 3 = 6.
4. 表达式可嵌套,[‘+’, 1, 2, [‘*‘, 1, 3]],这样结果为 1 + 2 + 1 * 3 = 6.
输入一定合法,不用考虑给了两个连续数字却没有运算符的情况,也不用考虑除数为0的情况。
Solution:
Use a stack. If the current token is not right square, ], push into the stack. Else, pop and computation until we see a left square, [. 

Code (Java):
import java.util.*;

public class Solution {
    public int expressionEvaluation(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        // Contains only one char
        if (s.length() == 3) {
            char c = s.charAt(1);
            if (Character.isDigit(c)) {
                return Character.getNumericValue(c);
            } else {
                if (c == '*') {
                    return 1;
                } else {
                    return 0;
                }
            }
        }
        
        Stack<String> stack = new Stack<>();
        
        String[] tokens = s.split(",");
        
        for (String token : tokens) {
            if (token.equals("[")) {
                stack.push("[");
            } else if (isNumeric(token)) {
                stack.push(token);
            } else if (isOperator(token)) {
                stack.push(token);
            } else if (token.equals("]")) {
                compute(stack);
            }
        }
        
        if (!stack.isEmpty()) {
            compute(stack);
        }
        
        return Integer.parseInt(stack.pop());
    }
    
    private boolean isNumeric(String s) {
        return Character.isDigit(s.charAt(0));
    }
    
    private boolean isOperator(String s) {
        return s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/");
    }
    
    private void compute(Stack<String> stack) {
        List<Integer> nums = new ArrayList<>();
        while (isNumeric(stack.peek())) {
            nums.add(Integer.parseInt(stack.pop()));
        }
        
        String op = stack.peek();
        
        // Pop out the left [
        stack.pop();
        
        computeHelper(stack, nums, op);
    }
    
    private void computeHelper(Stack<String> stack, List<Integer> nums, String op) {
        
        int prev = nums.get(0);
        
        for (int i = 1; i < nums.size(); i++) {
            int curr = nums.get(i);
            
            switch (op) {
                case "+" : prev = prev + curr;
                break;
                
                case "-" : prev = prev - curr;
                break;
                
                case "*" : prev = prev * curr;
                break;
                
                case "/" : prev = prev / curr;
            }
        }
        
        stack.push(prev + "");
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        String s = scanner.nextLine();
        
        Solution solution = new Solution();
        int result = solution.expressionEvaluation(s);
        
        System.out.println(result);
        
        scanner.close();
    }
} 

Note:
The current solution requires the input string is delimated by comma, even after the left square and before the right square. e.g. 
[,+,1,2,3,]

The purpose is to avoid the [ and + are splits into one string. 
One possible way out is just to parse the string characters by characters. When it meets a digit, parse it to a numeric number until it saw a comma or right square ]. 

No comments:

Post a Comment