leetcode-go/oj/bytedance-2019-interview/Calculator.java

import java.util.Scanner;
import java.util.Stack;

public class Calculator {
    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in)) {
            String str = sc.nextLine();
            System.out.println(calculate(str));
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    private static int calculate(String str) throws Exception {
        char[] exp = str.toCharArray();
        Stack<Character> ops = new Stack<>();
        Stack<Integer> num = new Stack<>();
        //   + - * / ( ) $
        // + > > < < < > >
        // - > > < < < > >
        // * > > > > < > >
        // / > > > > < > >
        // ( < < < < < =
        // E < < < < <   ac
        for (int i = 0; i <= exp.length;) {
            if (i == exp.length) {
                if (ops.isEmpty()) break;
                if (ops.peek() == '(') throw new Exception("Invalid expression!");
                num.push(operate(ops.pop(), num.pop(), num.pop()));
                continue;
            }
            switch (exp[i]) {
                case '+': case '-':
                    if (ops.isEmpty() || ops.peek() == '(') {
                        ops.push(exp[i++]);
                    } else {
                        num.push(operate(ops.pop(), num.pop(), num.pop()));
                    }
                    break;
                case '*': case '/':
                    if (ops.isEmpty() || ops.peek() == '(' || ops.peek() == '+' || ops.peek() == '-') {
                        ops.push(exp[i++]);
                    } else {
                        num.push(operate(ops.pop(), num.pop(), num.pop()));
                    }
                    break;
                case '(':
                    ops.push(exp[i++]);
                    break;
                case ')':
                    if (ops.isEmpty()) throw new Exception("Invalid expression!");
                    if (ops.peek() == '(') {
                        ops.pop();
                        i++;
                    } else {
                        num.push(operate(ops.pop(), num.pop(), num.pop()));
                    }
                    break;
                default:
                    int j;
                    for (j = i + 1; j < exp.length && '0' <= exp[j] && exp[j] <= '9'; j++);
                    int n = Integer.parseInt(str.substring(i, j));
                    num.push(n);
                    i = j;
            }
        }
        if (num.size() != 1) throw new Exception("Invalid expression!");
        return num.peek();
    }

    private static int operate(char op, int n2, int n1) throws Exception {
        switch (op) {
            case '+':
                return n1 + n2;
            case '-':
                return n1 - n2;
            case '*':
                return n1 * n2;
            case '/':
                if (n2 == 0) throw new Exception("Divided by 0!");
                return n1 / n2;
        }
        return 0;
    }
}