从反向波兰表示法（RPN）转换为树形式？

本文介绍了从反向波兰表示法（RPN）转换为树形式？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我不明白怎么做？有人可以解释如何将 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 + ")"); } }