我试图找出如何通过表达式树做不同的遍历。例如，如果I型在“ - + 10 * 2 8 3”，我希望它打印出来的前缀，后缀，以及表达的中缀的版本。
我还需要计算通过后序遍历的表达，这应该是评估函数的结果。
然而，当我运行我的程序，我只得到每个表达式的第一个字符。我的这些遍历是如何工作的错误认识？
编辑：按照建议，我救了buildtree的结果，也改变sc.next到sc.nextLine。
此外，每一个方法应该是递归的。
鉴于 “ - + 10 * 2 8 3”，预期的答案是：
prefix expression:
- + 10 * 2 8 3
postfix expression:
10 2 8 * + 3 -
infix expression:
( ( 10 + ( 2 * 8 ) ) - 3 )
Result = 23
我明白我还没有实现与括号中缀表达什么，不过没关系，现在。
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter a prefix expression: ");
Node root = buildTree(sc);
System.out.println("prefix expression: ");
infix(root);
System.out.println("postfix expression: ");
postfix(root);
System.out.println("infix expression: ");
infix(root);
System.out.print("Result = ");
evaluate(root);
}
static Node buildTree(Scanner sc) {
Node n = new Node(null);
int i = 0;
String prefixExpression = sc.nextLine();
String[] temp = prefixExpression.split(" ");
if(n.isLeaf()) {
n.value = temp[i];
n.left = null;
n.right = null;
i++;
}
return n;
}
static void infix(Node node) {
if(node.isLeaf()){
System.out.println(node.value);
}
else {
infix(node.left);
System.out.println(node.value + " ");
infix(node.right);
}
}
void prefix(Node node) {
if(node.isLeaf()){
System.out.println(node.value);
}
else {
switch(node.value) {
case "+":
System.out.print("+");
break;
case "-":
System.out.print("-");
break;
case "*":
System.out.print("*");
break;
case "/":
System.out.print("/");
break;
}
}
prefix(node.left);
System.out.print(" ");
prefix(node.right);
}
static void postfix(Node node) {
if(node.isLeaf()){
System.out.println(node.value);
}
else {
postfix(node.left);
postfix(node.right);
switch (node.value) {
case "+":
System.out.print("+");
break;
case "-":
System.out.print("-");
break;
case "*":
System.out.print("*");
break;
case "/":
System.out.print("/");
break;
}
}
}
public static int evaluate(Node node) {
if(node.isLeaf()) {
return Integer.parseInt(node.value);
}
else {
int leftHandSide = evaluate(node.getLeft());
int rightHandSide = evaluate(node.getRight());
String operator = node.getValue();
if("+".equals(operator)) {
return leftHandSide + rightHandSide;
}
else if("-".equals(operator)) {
return leftHandSide - rightHandSide;
}
else if("*".equals(operator)) {
return leftHandSide * rightHandSide;
}
else if("/".equals(operator)) {
return leftHandSide / rightHandSide;
}
else {
System.out.println("Unexpected problem. Error.");
}
return 0;
}
}
}
这里是Node.java，有getter和setter了。
public class Node<E> {
String value;
Node<E> left;
Node<E> right;
Node(String value){
left = null;
right = null;
this.value = value;
}
Node(String value, Node<E> left, Node<E> right) {
this.value = value;
this.left = left;
this.right = right;
}
boolean isLeaf() {
return (left == null && right == null);
}
编辑：
因为你的问题说：“ 如何做一个表达式树的遍历不同？，这个问题我可以在你的代码中看到正在建设的树（即buildTree()方法）。
为了解决这个问题，我已经使用buildExpressionTree(array)方法你的前缀输入转换为使用表达式树Stack的数据结构。
表达式树的结构：
构建表达式树我有使用堆栈。因为在你的情况下输入是前缀形式，以便循环通过输入表达式相反，做以下为每个字符。
在端部仅堆叠的元件将是表达式树的根。
另外在打印不同的遍历，你并不需要所有这些，如果条件检查不同operators.You可以简单地做遍历如下图所示我的代码。
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter a prefix expression: ");
String prefixExpression = sc.nextLine();
String[] temp = prefixExpression.split(" ");
Node n = null;
n = buildExpressionTree(temp);
System.out.println("prefix expression: ");
prefix(n);
System.out.println();
System.out.println("postfix expression: ");
postfix(n);
System.out.println();
System.out.println("infix expression: ");
infix(n);
System.out.println();
int result = evaluate(n);
System.out.print("Result = "+ result);
}
static Node buildExpressionTree(String[] input) {
Stack<Node> st = new Stack();
Node t, t1, t2;
// Traverse through every character of
// input expression
for (int i = (input.length-1); i >= 0; i--) {
// If operand, simply push into stack
if (isNumber(input[i])) {
t = new Node(input[i]);
st.push(t);
} else // operator
{
t = new Node(input[i]);
// Pop two top nodes
// Store top
t1 = st.pop(); // Remove top
t2 = st.pop();
// make them children
t.left = t1;
t.right = t2;
st.push(t);
}
}
t = st.peek();
st.pop();
return t;
}
static boolean isNumber(String s) {
boolean numeric = true;
try {
Integer num = Integer.parseInt(s);
} catch (NumberFormatException e) {
numeric = false;
}
return numeric;
}
static void infix(Node node) {
if( null == node) {
return;
}
infix(node.left);
System.out.print(node.value + " ");
infix(node.right);
}
static void prefix(Node node) {
if( null == node) {
return;
}
System.out.print(node.value+ " ");
prefix(node.left);
prefix(node.right);
}
static void postfix(Node node) {
if( null == node) {
return;
}
postfix(node.left);
postfix(node.right);
System.out.print(node.value+ " ");
}
public static int evaluate(Node node) {
if(node.isLeaf()) {
return Integer.parseInt(node.value);
}
else {
int leftHandSide = evaluate(node.left);
int rightHandSide = evaluate(node.right);
String operator = node.value;
if("+".equals(operator)) {
return leftHandSide + rightHandSide;
}
else if("-".equals(operator)) {
return leftHandSide - rightHandSide;
}
else if("*".equals(operator)) {
return leftHandSide * rightHandSide;
}
else if("/".equals(operator)) {
return leftHandSide / rightHandSide;
}
else {
System.out.println("Unexpected problem. Error.");
}
return 0;
}
}
OUTPUT：
Enter a prefix expression:
- + 10 * 2 8 3
prefix expression:
- + 10 * 2 8 3
postfix expression:
10 2 8 * + 3 -
infix expression:
10 + 2 * 8 - 3
Result = 23
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句