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 + ")");
    }
}

Answer 2

我将使用一个类Node来表示树的节点。我所有的节点需要如下：

public interface Node<T> {
    public void addChild(Node<T>);
}

我们将假设我有一个TreeNode<T>具有构造函数的实现类public TreeNode(T value)。

我将假设您已经切碎了字符串并以其他方法解析了所有字符，因此您有一个Token表示表达式的 s 数组：

public interface Token {

    /**
     * @return The number of operands this token takes.
     * A return value of 0 indicates this token does not
     * take any operands.
     */
    public int getOperandCount();

}

（可能需要在您的类中包含其他方法，以便您可以从树中读取值，但这并不是构建它所必需的。）

还，

public class MalformedExpressionException extends IllegalArgumentException{
    public MalformedExpressionException(String reason){/* [ ... ] */};
    // [ ... ]
}

有了这个，下面的函数将为你生成一棵树，返回它的根节点。

public static Node<Token> makeTree(Token [] tokens){
    Stack<Node<Token>> stack = new Stack<>();

    try{
        for(Token t:tokens){
            Node<Token> node = new TreeNode<Token>(t);
            for(int idx = 0; idx < t.getOperandCount(); idx++)
                node.addChild(stack.pop());
            stack.push(node);
        }
    }catch (EmptyStackException e){
        throw new MalformedExpressionException("too few operands");
    }

    if(stack.size() != 1)
        throw new MalformedExpressionException("too many operands");

    return stack.pop();
}