Expression evaluation

use stack

1. Basic calculator

   public int calculate(String s) {
        if (s == null || s.length() == 0) {
            return -1;
        }
   
        Stack<Integer> stack = new Stack<>();
        int op = 1;
        int num = 0;
        int res = 0;
        int i = 0;
   
        while (i < s.length()) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    num = num * 10 + s.charAt(i) - '0';
                    i++;
                }
                res += num * op;
            }
            else if (c == '+') {
                op = 1;
                num = 0;
                i++;
            }
            else if (c == '-') {
                op = -1;
                num = 0;
                i++;
            }
            else if (c == '(') {
                stack.push(res);
                stack.push(op);
                res = 0;
                op = 1;
                i++;
            }
            else if (c == ')') {
                op = stack.pop();
                num = stack.pop();
                res = num + res * op;
                i++;
            }
            else {
                i++;
            }
        }
        return res;
    }
   

2. Basic calculator II

   public int calculate(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }    
        Stack<Integer> stack = new Stack<>();
        int op = 0, num = 0;
        int res = 0;
        int i = 0;
        while (i < s.length()) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                    num = num * 10 + s.charAt(i) - '0';
                    i++;
                }
   
                if (op == 3 || op == 4) {
                    int t = stack.pop();
                    if (op == 3)
                        res = t * num;
                    else 
                        res = t / num;
                    stack.push(res);
                }
                else
                    stack.push(num);
            }
            else if (c == '+') {
                op = 1;
                stack.push(op);
                num = 0;
                i++;
            }
            else if (c == '-') {
                op = 2;
                stack.push(op);
                num = 0;
                i++;
            }
            else if (c == '*') {
                op = 3;
                num = 0;
                i++;
            }
            else if (c == '/') {
                op = 4;
                num = 0;
                i++;
            }
            else {
                i++;
            }
        }
        res = 0;
        while (stack.size() > 1) {
            int a = stack.pop();
            op = stack.pop();
            res = op == 1 ? res + a : res - a;
        }
        res += stack.pop();
        return res;
    }
   

3. Evaluate Reverse Polish Notation

public int evalRPN(String[] tokens) {
        if (tokens == null || tokens.length == 0) {
            return 0;
        }

        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < tokens.length; i++) {
            String s = tokens[i];
            if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
                int b = stack.pop();
                int a = stack.pop();
                stack.push(evaluate(a, b, s));
            } else {
                stack.push(Integer.parseInt(s));
            }
        }
        return stack.pop();
    }

    public int evaluate(int a, int b, String token) {
        switch (token) {
            case "+" : return a + b;
            case "-" : return a - b;
            case "*" : return a * b;
            case "/" : return a / b;
            default  : return 0;
        }
    }

1. Expression Add Operators: add operators to a string of numbers

public List<String> addOperators(String num, int target) {
    List<String> res = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    dfs(res, sb, num, 0, target, 0, 0);
    return res;

}
public void dfs(List<String> res, StringBuilder sb, String num, int pos, int target, long prev, long multi) { 
    if(pos == num.length()) {
        if(target == prev) res.add(sb.toString());
        return;
    }
    for(int i = pos; i < num.length(); i++) {
        if(num.charAt(pos) == '0' && i != pos) break;
        long curr = Long.parseLong(num.substring(pos, i + 1));
        int len = sb.length();
        if(pos == 0) {
            dfs(res, sb.append(curr), num, i + 1, target, curr, curr); 
            sb.setLength(len);
        } else {
            dfs(res, sb.append("+").append(curr), num, i + 1, target, prev + curr, curr); 
            sb.setLength(len);
            dfs(res, sb.append("-").append(curr), num, i + 1, target, prev - curr, -curr); 
            sb.setLength(len);
            dfs(res, sb.append("*").append(curr), num, i + 1, target, prev - multi + multi * curr, multi * curr); 
            sb.setLength(len);
        }
    }
}

1. Different Ways to Add Parentheses:

divide into left and right half and recursively solve

public List<Integer> diffWaysToCompute(String input) {
        List<Integer> res = new ArrayList<>();
        if (input.length() == 0) {
            return res;
        }

        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (c == '+' || c == '-' || c == '*') {
                String left = input.substring(0, i);
                String right = input.substring(i+1);
                List<Integer> l = diffWaysToCompute(left);
                List<Integer> r = diffWaysToCompute(right);
                for (int a : l) {
                    for (int b : r) {
                        res.add(eval(a, b, c));
                    }
                }
            }
        }
        if (res.size() == 0) {
            res.add(Integer.parseInt(input));
        }

        return res;
    }

    public int eval(int a, int b, char c) {
        switch(c) {
            case '+' : return a + b;
            case '-' : return a - b;
            case '*' : return a * b;
            default  : return -1;
        }
    }