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

/*
 * 思路：
 * 1. 将中缀表达式转换为后缀表达式（逆波兰表达式）。
 * 2. 使用栈构建二叉表达式树。
 * 
 * 第一步：
 * - 使用栈和优先级规则将中缀表达式转换为后缀表达式。
 * 
 * 第二步：
 * - 使用一个栈来构建树。当遇到操作数时，创建一个叶节点并推入栈中。
 * - 当遇到运算符时，弹出栈顶的两个节点作为该运算符的子节点，创建一个新节点并将其推入栈中。
 */

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

class TreeNode {
    char val;
    TreeNode left;
    TreeNode right;
    TreeNode(char x) { val = x; }
}

class Solution {
    public TreeNode expTree(String s) {
        List<Character> postfix = infixToPostfix(s);
        Deque<TreeNode> stack = new ArrayDeque<>();
        postfix.forEach(c -> {
            if (Character.isDigit(c)) {
                stack.push(new TreeNode(c));
            } else {
                TreeNode node = new TreeNode(c);
                node.right = stack.pop();
                node.left = stack.pop();
                stack.push(node);
            }
        });
        return stack.peek();
    }

    private List<Character> infixToPostfix(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        Map<Character, Integer> precedence = Map.of(
            '+', 1, '-', 1, '*', 2, '/', 2, '(', 0
        );
        return IntStream.range(0, s.length())
            .mapToObj(s::charAt)
            .flatMap(c -> {
                if (Character.isDigit(c)) {
                    return Stream.of(c);
                } else if (c == '(') {
                    stack.push(c);
                    return Stream.empty();
                } else if (c == ')') {
                    List<Character> list = new ArrayList<>();
                    while (!stack.isEmpty() && stack.peek() != '(') {
                        list.add(stack.pop());
                    }
                    stack.pop();
                    return list.stream();
                } else {
                    List<Character> list = new ArrayList<>();
                    while (!stack.isEmpty() && precedence.get(stack.peek()) >= precedence.get(c)) {
                        list.add(stack.pop());
                    }
                    stack.push(c);
                    return list.stream();
                }
            })
            .collect(Collectors.toList());
    }
}