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

    private static void operate(Stack<Character> ops, Stack<Double> num) throws Exception {
        if (num.size() < 2) throw new Exception("Invalid expression!");
        char op = ops.pop();
        double n2 = num.pop(), n1 = num.pop();
        switch (op) {
            case '+':
                num.push(n1 + n2);
                break;
            case '-':
                num.push(n1 - n2);
                break;
            case '*':
                num.push(n1 * n2);
                break;
            case '/':
                if (n2 == 0.0) throw new Exception("Divided by 0!");
                num.push(n1 / n2);
                break;
        }
    }
}