随笔练习

import java.util.Stack;

/**
 * @author 西城风雨楼
 */
public class ExpressionTree {
    private TreeNode root;

    private ExpressionTree() {
    }

    /**
     * 从后缀表达式构建一棵表达式树
     *
     * @param suffix 后缀表达式
     * @return 返回构建完毕的表达式树
     */
    public static ExpressionTree createFromSuffix(String suffix) {
        Stack<TreeNode> stack = new Stack<>();
        char[] ops = suffix.toCharArray();
        for (char op : ops) {
            // 如果是一个运算符
            if (!isBasicOperator(op)) {
                stack.push(new TreeNode(op + "", null, null));
            } else {
                // 如果是运算符的话
                TreeNode right = stack.pop();
                TreeNode left = stack.pop();
                TreeNode root = new TreeNode(op + "", left, right);
                stack.push(root);
            }
        }
        ExpressionTree expressionTree = new ExpressionTree();
        expressionTree.root = stack.pop();
        return expressionTree;
    }

    /**
     * 实现对表达式树的先序遍历
     *
     * @return 返回先序遍历的结果
     */
    public String preOrder() {
        StringBuilder res = new StringBuilder();
        if (root == null) {
            return res.toString();
        }

        TreeNode cur = root;
        while (cur != null) {
            if (cur.left != null) {
                TreeNode mostRight = cur.left;
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {
                    // 说明这是第一次访问cur
                    res.append(cur.data);
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    mostRight.right = null;
                }
            } else {
                res.append(cur.data);
            }
            cur = cur.right;
        }
        return res.toString();
    }

    /**
     * 将表达式树的右孩子反转
     *
     * @param root 表达式树的根节点
     * @return 返回反转后的节点引用
     */
    private TreeNode reverseWithRight(TreeNode root) {
        TreeNode pre = null;
        TreeNode cur = root;
        TreeNode next;

        while (cur != null) {
            next = cur.right;
            cur.right = pre;
            pre = cur;
            cur = next;
        }

        return pre;
    }

    public String postOrder() {
        StringBuilder res = new StringBuilder();
        if (root == null) {
            return res.toString();
        }

        TreeNode cur = root;
        while (cur != null) {
            if (cur.left != null) {
                TreeNode mostRight = cur.left;
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {
                    // 说明是第一次到达
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    // 如果是第二次到达
                    mostRight.right = null;
                    record(cur.left, res);
                }
            }
            cur = cur.right;
        }
        record(root, res);
        return res.toString();
    }

    private void record(TreeNode root, StringBuilder res) {
        TreeNode reverse = reverseWithRight(root);
        TreeNode cur = reverse;
        while (cur != null) {
            res.append(cur.data);
            cur = cur.right;
        }
        reverseWithRight(reverse);
    }

    /**
     * 实现表达式树的中序遍历
     *
     * @return 返回表达式树的中序遍历的结果
     */
    public String inOrder() {
        StringBuilder res = new StringBuilder();
        if (root == null) {
            return res.toString();
        }

        TreeNode cur = root;
        while (cur != null) {
            if (cur.left != null) {
                TreeNode mostRight = cur.left;
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {
                    // 如果是第一次访问
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    res.append(cur.data);
                    mostRight.right = null;
                }
            } else {
                res.append(cur.data);
            }
            cur = cur.right;
        }
        return res.toString();
    }

    /**
     * 判断指定的字符是否是基本运算符
     *
     * @param c 带判定的字符
     * @return 如果该字符是基本运算符，那么返回true，否则返回false
     */
    private static boolean isBasicOperator(char c) {
        return c == '+' || c == '-' || c == '*' || c == '/';
    }

    /**
     * 表达式树的节点类型
     */
    private static class TreeNode {
        public String data;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(String data, TreeNode left, TreeNode right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 根据前缀表达式和中缀表达式，重新构建一棵表达式树
     *
     * @param preOrder 前缀表达式
     * @param inOrder  中缀表达式
     * @return 返回重构的表达式树
     */
    public static ExpressionTree rebuildExpressionTree(String preOrder, String inOrder) {
        TreeNode root = rebuildHelper(preOrder.toCharArray(),
                0,
                preOrder.length() - 1,
                inOrder.toCharArray(),
                0,
                inOrder.length());
        ExpressionTree expressionTree = new ExpressionTree();
        expressionTree.root = root;
        return expressionTree;
    }

    /**
     * 根据前缀表达式和中缀表达式重构表达式树，该函数不对前缀表达式和后缀表达式的
     * 合法性做任何保证，如果传入的表达式不合法，或者两个序列根本不可能构成一棵表
     * 达式树，那么可能会失败
     *
     * @param preOrder 前缀表达式
     * @param preLeft  前缀表达式的起始位置
     * @param preRight 前缀表达式的结束位置
     * @param inOrder  中缀表达式
     * @param inLeft   中缀表达式的起始位置
     * @param inRight  中缀表达式的结束位置
     * @return 返回重构完毕的表达式树
     */
    private static TreeNode rebuildHelper(char[] preOrder,
                                          int preLeft,
                                          int preRight,
                                          char[] inOrder,
                                          int inLeft,
                                          int inRight) {
        // 创建表达式树的根节点
        TreeNode root = new TreeNode(preOrder[preLeft] + "", null, null);

        if (preLeft == preRight) {
            // 如果只有一个元素，那么直接返回
            return root;
        }

        // 找到根节点在中缀表达式中的位置
        // 获得该位置是为了划分根节点左子树和右子树的范围
        int pos = Integer.MIN_VALUE;
        for (int i = inLeft; i <= inRight; i++) {
            if (inOrder[i] == preOrder[preLeft]) {
                pos = i;
                break;
            }
        }
        if (pos == Integer.MIN_VALUE) {
            throw new RuntimeException("构建失败");
        }
        int leftChildSize = pos - inLeft;
        root.left = rebuildHelper(
                preOrder,
                preLeft + 1,
                preLeft + leftChildSize,
                inOrder,
                inLeft,
                pos - 1);
        root.right = rebuildHelper(preOrder,
                preLeft + leftChildSize + 1,
                preRight,
                inOrder,
                pos + 1,
                inRight);
        return root;
    }

    public static void main(String[] args) {
        ExpressionTree expressionTree = ExpressionTree.createFromSuffix("ab+cde+**");
        System.out.println(expressionTree.preOrder());
        System.out.println(expressionTree.inOrder());
        System.out.println(expressionTree.postOrder());
        ExpressionTree rebuild = ExpressionTree.rebuildExpressionTree("*+ab*c+de", "a+b*c*d+e");
        System.out.println("重构:");
        System.out.println(rebuild.preOrder());
        System.out.println(rebuild.inOrder());
        System.out.println(rebuild.postOrder());
    }
}