从反向波兰表示法（RPN）转换为树形式？ [英] Converting from reverse Polish notation(RPN) into a tree form?

问题描述

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

I dont understand how to do this? Can someone please explain how to convert, for example, ac+ ac+*into a binary tree form?? I need to turn this expression into a full parenthesized string representation of this tree.

推荐答案

您需要按照方式构建树你会处理后缀输入。但是，当您遇到某个操作时，不会计算该值，而是将堆栈上的参数作为运算符节点的子节点。然后你把它推到堆栈上（就像你在后缀表示法中将计算结果推到堆栈上一样）。

You need to build the tree just the way you would process the postfix input. However, when you encounter an operation, instead of calculating the value, you make the arguments on the stack the children of the operator node. Then you push it on the stack (just as you would push the calculation result on the stack in postfix notation).

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

At the end, the only element on the stack should be the root of the complete tree.

应该大致如下：

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

这篇关于从反向波兰表示法（RPN）转换为树形式？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！