java - 从逆波兰表示法(RPN)转换为树形式？

Question

我不明白该怎么做？有人可以解释一下如何将 ac+ ac+* 转换为二叉树形式吗？我需要将此表达式转换为该树的完整括号字符串表示形式。

Answer 1

您需要按照处理后缀输入的方式构建树。但是，当您遇到操作时，您不是计算值，而是将堆栈上的参数设置为操作符节点的子节点。然后将其压入堆栈(就像将计算结果以后缀表示法压入堆栈一样)。

最后，堆栈上的唯一元素应该是完整树的根。

应该看起来大致像这样:

public class Node {
    char value;
    Node left, right;

    public Node(char value) {
        this.value = value;
    }

    public static Node parseUpn(String s) {
        Stack<Node> stack = new Stack<Node>();

        for (char c: s.toCharArray()) {
            if (c != ' ') {
                Node node = new Node(c);
                if ("+-*/".indexOf(c) != -1) { 
                    node.right = stack.pop();
                    node.left = stack.pop();
                }
            }
            stack.push(node);
        }

        if (stack.size() != 1) {
            throw new RuntimeException("Expected exactly one stack value.");
        }
        return stack.pop();
    }

    @Override
    public String toString() {
        return left == null ? String.valueOf(value) : 
             ("(" + left + " " + value + " " + right + ")");
    }
}