题解 | 表达式求值

import java.util.*;

public class Solution {
    public int solve (String s) {
        //优先级高的直接入栈，优先级低的或同级的入栈先把高的同级的弹出来
        //( 直接入栈  遇到)一直出到(为止
        Deque<String> stack1 = new ArrayDeque<>(), stack2 = new ArrayDeque<>();
        //stack1入运算符   stack2为后缀表达式
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if ('0' <= c && c <= '9') {
                str.append(c);
            } else {
                if (str.length() != 0) {
                    stack2.push(str.toString());
                    str.delete(0, str.length());
                }
                if (c == '(') {
                    stack1.push(Character.toString(c));
                } else if (c == '*') {
                    if (!stack1.isEmpty()) {
                        while (stack1.peek().charAt(0) == '*') {
                            stack2.push(stack1.pop());
                        }
                        stack1.push(Character.toString(c));
                        continue;
                    }
                    stack1.push(Character.toString(c));
                } else if (c == '+' || c == '-') {
                    if (!stack1.isEmpty()) {
                        while ((!stack1.isEmpty() && stack1.peek().charAt(0) == '+' ) ||
                                (!stack1.isEmpty() && stack1.peek().charAt(0) == '-' ) ||
                                (!stack1.isEmpty() && stack1.peek().charAt(0) == '*')) {
                            stack2.push(stack1.pop());
                        }
                        stack1.push(Character.toString(c));
                        continue;
                    }
                    stack1.push(Character.toString(c));
                } else if (c == ')') {
                    while (stack1.peek().charAt(0) != '(') {
                        stack2.push(stack1.pop());
                    }
                    stack1.pop();
                }
            }
        }
        List<String> list = new ArrayList<>();
        if (str.length() != 0)stack2.push(str.toString());
        while (!stack2.isEmpty()) {
            list.add(stack2.pop());
        }
        Collections.reverse(list);
        while (!stack1.isEmpty()) {
            list.add(stack1.pop());
        }
        // for(int i=0;i<list.size();i++){
        //     System.out.printf("%s ",list.get(i));
        // }
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i).charAt(0) == '+') {
                int a = Integer.parseInt(stack1.pop());
                int b = Integer.parseInt(stack1.pop());
                stack1.push(Integer.toString(a + b));
                continue;
            }
            if (list.get(i).charAt(0) == '-') {
                int a = Integer.parseInt(stack1.pop());
                int b = Integer.parseInt(stack1.pop());
                stack1.push(Integer.toString(b-a));
                continue;
            }
            if (list.get(i).charAt(0) == '*') {
                int a = Integer.parseInt(stack1.pop());
                int b = Integer.parseInt(stack1.pop());
                stack1.push(Integer.toString(a*b));
                continue;
            }
            stack1.push(list.get(i));
        }
        return Integer.parseInt(stack1.pop());
    }
}