DataSection88

// Guide to Data Structures
// Section 8.8
// Copyright 2018, by J.T. Streib and T. Soma

import java.util.*;

class PrefixToInfix {
public static void main(String [] args){
  Scanner scanner;
  scanner = new Scanner(System.in);

  BinaryExpressionTreeGeneric tree;
  tree = new BinaryExpressionTreeGeneric();

  tree.createTree();
  System.out.println();

  tree.inFix();
  System.out.println();
}
}

import java.util.*;

public class BinaryExpressionTreeGeneric<T> {
private NodeGeneric root;

public BinaryExpressionTreeGeneric( ) {
  root = null;
}

public void createTree(){
  System.out.println();
  System.out.println("Enter a prefix arithmetic expression.");
  System.out.println();
  root=inputData();
}

private NodeGeneric inputData() {
  Scanner scanner;
  scanner = new Scanner(System.in);

  System.out.print("Enter an operator or operand: ");
  char ch = scanner.next().charAt(0);
  NodeGeneric p = new NodeGeneric(ch);
  if( ch == '+' || ch =='-' || ch == '*' || ch == '/' ) {
     p.left=inputData();
     p.right=inputData();
  }
  return p;
}

public void inFix(){
  System.out.print("Infix: ");
  inOrder(root);
  System.out.println();
}

private void inOrder(NodeGeneric ptr) {
  if(ptr.left!=null && ptr.right!=null){
     System.out.print("(");
     inOrder(ptr.left);
     System.out.print(" " + ptr.data + " ");
     inOrder(ptr.right);
     System.out.print(")");
  }
  else
     System.out.print(ptr.data);
}

// Inner Class: NodeGeneric
class NodeGeneric<T> {
  private NodeGeneric<T> left;
  private T data;
  private NodeGeneric<T> right;

  public NodeGeneric(){
     this(null);
  }

  public NodeGeneric(T data) {
     left = null;
     this.data = data;
     right = null;
  }
}
}