表达式值计算

通用解法：将中缀表达式转换为后缀表达式

• 1.遇到数字，直接存入后缀
• 2.遇到(，入栈
• 3.遇到)，不断弹出栈顶元素，直到遇到(
• 4.遇到其他运算符，不断弹出优先级大于等于当前运算符的的元素，最后将当前运算符入栈。*,/优先级大于+,-
• 5.最后弹出栈中元素，直到栈空

224. 基本计算器

1597. 根据中缀表达式构造二叉表达式树

public List<String> getPostfix(String s) {
    s = s.trim();
    if (s.charAt(0) == '-') s = "0" + s;
    List<String> ans = new ArrayList<>();
    Deque<Character> q = new LinkedList<>();
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == ' ') continue;
        if (s.charAt(i) == '(') {
            q.offerLast(s.charAt(i));
            if (s.charAt(i + 1) == '-') ans.add("0");
        } else if (s.charAt(i) == ')') {
            while (!q.isEmpty() && q.peekLast() != '(') {
                ans.add("" + q.pollLast());
            }
            q.pollLast();
        } else if (s.charAt(i) == '+' || s.charAt(i) == '-') {
            while (!q.isEmpty() && q.peekLast() != '(') {
                ans.add("" + q.pollLast());
            }
            q.offerLast(s.charAt(i));
        } else if (s.charAt(i) == '*' || s.charAt(i) == '/') {
            while (!q.isEmpty() && (q.peekLast() == '*' || q.peekLast() == '/')) {
                ans.add("" + q.pollLast());
            }
            q.offerLast(s.charAt(i));
        } else {
            int l = i;
            while (i < s.length() && Character.isDigit(s.charAt(i))) {
                i++;
            }
            ans.add(s.substring(l, i--));
        }
    }
    while (!q.isEmpty()) {
        ans.add("" + q.pollLast());
    }
    return ans;
}