表达式计算

后缀表达式计算

题目详情可见 150. 逆波兰表达式求值

xxxxxxxxxx
public int evalRPN(String[] tokens) {
        Deque<Integer> st = new ArrayDeque<>();
        for (String t : tokens) {
            if (t.equals("+")) {
                int n1 = st.poll(), n2 = st.poll();
                st.push(n1 + n2);
            } else if (t.equals("-")) {
                int n1 = st.poll(), n2 = st.poll();
                st.push(n2 - n1);
            } else if (t.equals("*")) {
                int n1 = st.poll(), n2 = st.poll();
                st.push(n1 * n2);
            } else if (t.equals("/")) {
                int n1 = st.poll(), n2 = st.poll();
                st.push(n2 / n1);
            } else st.push(Integer.parseInt(t));
        }
        return st.peek();
    }

中缀表达式计算

题目详情可见 面试题 16.26. 计算器、227. 基本计算器 II、表达式求值、表达式求值

上面四个题目均可用同一个模版，推荐文章 【宫水三叶】使用「双栈」解决「究极表达式计算」问题

class Solution {

    private Map<Character, Integer> map = new HashMap<>(){{
        put('+', 1);
        put('-', 1);
        put('*', 2);
        put('/', 2);
        put('%', 2);
        put('^', 3);
    }};

    public int calculate(String s) {
        s = s.replaceAll(" ", "");
        char[] cs = s.toCharArray();
        int n = s.length();
        Deque<Integer> nums = new ArrayDeque<>();
        nums.addLast(0);
        Deque<Character> ops = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            char c = cs[i];
            if (c == '(') {
                ops.addLast(c);
            } else if (c == ')') {
                while (!ops.isEmpty()) {
                    if (ops.peekLast() != '(') calc(nums, ops);
                    else {
                        ops.pollLast();
                        break;
                    }
                }
            } else {
                if (isNum(c)) {
                    int u = 0, j = i;
                    while (j < n && isNum(cs[j])) u = u * 10 + (cs[j++] - '0');
                    nums.addLast(u);
                    i = j - 1;
                } else {
                    if (i > 0 && (cs[i - 1] == '(' || cs[i - 1] == '+' || cs[i - 1] == '-')) {
                        nums.addLast(0);
                    }
                    while (!ops.isEmpty() && ops.peekLast() != '(') {
                        char prev = ops.peekLast();
                        if (map.get(prev) >= map.get(c)) {
                            calc(nums, ops);
                        } else break;
                    }
                    ops.addLast(c);
                }
            }
        }
        while (!ops.isEmpty()) calc(nums, ops);
        return nums.peekLast();
    }

    private void calc(Deque<Integer> nums, Deque<Character> ops) {
        if (nums.isEmpty() || nums.size() < 2) return ;
        if (ops.isEmpty()) return ;
        int b = nums.pollLast(), a = nums.pollLast();
        char op = ops.pollLast();
        int ans = 0;
        if (op == '+') ans = a + b;
        else if (op == '-') ans = a - b;
        else if (op == '*') ans = a * b;
        else if (op == '/') ans = a / b;
        else if (op == '%') ans = a % b;
        else if (op == '^') ans = (int) Math.pow(a, b);
        nums.addLast(ans);
    }

    private boolean isNum(char c) {
        return Character.isDigit(c);
    }
}