0
我已经编写了一个以中缀表示法表达的代码，并将表达式转换为二叉树。我不确定我在做什么错，但是我有程序编译但输出不正确，它应该打印出原始语句，然后打印没有括号的inorder语句，然后预订语句& postorder语句。我需要修正哪些问题才能获得正确的输出结果？中缀向二叉树转换器的错误输出
我的电流输出：
((6 + 2) - 5) * 8/2
*
*
*
正确的输出：
((6 + 2) - 5) * 8/2
6 + 2 - 5 * 8/2
/* - + 6 2 5 8 2
6 2 + 5 - 8 * 2/
我的主要方法：
public class Prog5 {
public static void main(String[] args) {
InFixToBinaryTreeConverter fp = new InFixToBinaryTreeConverter();
fp.run("((6 + 2) - 5) * 8/2");
}
}
我的节点类：
public class Node<String> {
protected String element;
protected Node<String> left;
protected Node<String> right;
int x;
public Node(String e, Node left, Node right){
element = e; //data = element
this.left = this.right = null;
}
}
我InFixToBinaryTreeConverter类：
public class InFixToBinaryTreeConverter{
List<String> stack = new ArrayList<>(); //stack
List<String> inFix= new LinkedList<>(); //queue
List<Node> btstack = new ArrayList<>(); //stack
private String expression;
Node root = null;
//create a no-arg consutrctor that initializes the inFix, stack , & btstack lists
InFixToBinaryTreeConverter(){
this.inFix = inFix;
this.stack = stack;
this.btstack = btstack;
}
public void run(String s){ // run method is driver for program
this.expression = s;
System.out.println(expression);
createInFix();
createBinaryTree();
printInorder(btstack.get(0));
System.out.println();
printPreorder(btstack.get(0));
System.out.println();
printPostorder(btstack.get(0));
}
public void createInFix(){
String[] temporary = expression.split("\\s+");
for (int i = 0; i < temporary.length; i++){
inFix.add(temporary[i]);
}
}
public void createBinaryTree(){
stack.add("(");
inFix.add(")");
while(!inFix.isEmpty()){
String variable = inFix.remove(0);
if(isANumber(variable)){
Node nodeNew = new Node(variable, null, null);
btstack.add(nodeNew);
}
else if(isLeftParentheses(variable)){
stack.add(variable);
}
if(isOperator(variable)){
while(precedence(stack.get(stack.size() - 1), variable)){
Node rightChild = btstack.remove(btstack.size() - 1);
Node leftChild = btstack.remove(btstack.size() - 1);
Node nodeNew = new Node(variable, rightChild, leftChild);
btstack.add(nodeNew);
}
stack.add(variable);
}
if(isRightParentheses(variable)){
if(stack.get(stack.size() -1) != null){
while(!isLeftParentheses(stack.get(stack.size() - 1))){
String temporary = stack.remove(stack.size() - 1);
Node rightChild2 = btstack.remove(btstack.size() - 1);
Node leftChild2 = btstack.remove(btstack.size() - 1);
btstack.add(new Node(temporary, leftChild2, rightChild2));
}
}
}
}
}
public static boolean isANumber(String str){
boolean isANumber = false;
if(str.charAt(0) >= '0' && str.charAt(0) <= '9'){
isANumber = true;
}
return isANumber;
}
public static boolean isOperator(String str){ //check to see if c is an operator
boolean isOperator = false;
if("+".equals(str) || "-".equals(str) || "*".equals(str) || "/".equals(str)){
return true;
}
return isOperator;
}
public boolean precedence(String operator1, String operator2){
boolean precedence = false;
int compareTo = operator1.compareTo(operator2);
if(compareTo >= 0){
precedence = true;
}
return precedence;
}
public boolean isLeftParentheses(String x) {
boolean isLeftParentheses = false;
if(x.equals("(")){
isLeftParentheses = true;
}
return isLeftParentheses;
}
public boolean isRightParentheses(String x) {
boolean isRightParentheses = false;
if(x.equals(")")){
isRightParentheses = true;
}
return isRightParentheses;
}
public void process(Node node){
System.out.print(node.elementr+ " ");
}
/* Given a binary tree, print its nodes in inorder*/
public void printInorder(Node node){
if (node != null){
printInorder(node.left); // first recur on left child
process(node); // then print the data of node
printInorder(node.right); // now recur on right child
}
}
/* Given a binary tree, print its nodes in preorder*/
public void printPreorder(Node node){
if (node != null){
process(node); // first print data of node
printPreorder(node.left); // then recur on left sutree
printPreorder(node.right); // now recur on right subtree
}
}
public void printPostorder(Node node){
if (node != null){
printPreorder(node.left); // then recur on left sutree
printPreorder(node.right); // now recur on right subtree
process(node); // first print data of node
}
}
}