ExpressionTree:后缀到Infix

Question

我在让我的toString()方法工作和打印括号时有问题。在我的指南针里。例如，现在如果我输入12+3*，它就会打印出1 + 2 * 3。我想把((1+2) *3)打印出来。

此外，当表达式树在输入中包含一个空格时，我想要构建它。例如，现在如果我输入12+，它可以工作，但是我希望能够输入1 2 +，而且它仍然工作。有什么想法吗？

忽略我的评估方法，我还没有实现它！

 // Java program to construct an expression tree

import java.util.EmptyStackException;
import java.util.Scanner;
import java.util.Stack;

import javax.swing.tree.TreeNode;

// Java program for expression tree
class Node {

    char ch;
    Node left, right;

    Node(char item) {
        ch = item;
        left = right = null;
    }
    public String toString() {
        return (right == null && left == null) ? Character.toString(ch) : "(" + left.toString()+ ch + right.toString() + ")";
    }

}

class ExpressionTree {

    static boolean isOperator(char c) {
        if (    c == '+' || 
                c == '-' || 
                c == '*' || 
                c == '/'
               ) {
            return true;
        }
        return false;
    }

    // Utility function to do inorder traversal
    public void inorder(Node t) {
        if (t != null) {
            inorder(t.left);
            System.out.print(t.ch + " ");
            inorder(t.right);
        }
    }

    // Returns root of constructed tree for given
    // postfix expression
    Node constructTree(char postfix[]) {
        Stack<Node> st = new Stack();
        Node t, t1, t2;


        for (int i = 0; i < postfix.length; i++) {

            // If operand, simply push into stack
            if (!isOperator(postfix[i])) {
                t = new Node(postfix[i]);
                st.push(t);
            } else // operator
            {
                t = new Node(postfix[i]);

                // Pop two top nodes
                // Store top
                t1 = st.pop();      // Remove top
                t2 = st.pop();

                //  make them children
                t.right = t1;
                t.left = t2;

                // System.out.println(t1 + "" + t2);
                // Add this subexpression to stack
                st.push(t);
            }
        }

        //  only element will be root of expression
        // tree
        t = st.peek();
        st.pop();

        return t;
    }

    public static void main(String args[]) {
        Scanner input = new Scanner(System.in);
        /*boolean keepgoing = true;
        while (keepgoing) {
            String line = input.nextLine();
            if (line.isEmpty()) {
                keepgoing = false;
            } else {
                Double answer = calculate(line);
                System.out.println(answer);
            }
        }*/
        ExpressionTree et = new ExpressionTree();
        String postfix = input.nextLine();
        char[] charArray = postfix.toCharArray();
        Node root = et.constructTree(charArray);
        System.out.println("infix expression is");
        et.inorder(root);
    }


    public double evaluate(Node ptr)
    {
        if (ptr.left == null && ptr.right == null)
            return toDigit(ptr.ch);
        else
        {
            double result = 0.0;
            double left = evaluate(ptr.left);
            double right = evaluate(ptr.right);
            char operator = ptr.ch;

            switch (operator)
            {
            case '+' : result = left + right; break;
            case '-' : result = left - right; break;
            case '*' : result = left * right; break;
            case '/' : result = left / right; break;
            default  : result = left + right; break;
            }
            return result;
        }
    }
    private boolean isDigit(char ch)
    {
        return ch >= '0' && ch <= '9';
    }
    private int toDigit(char ch)
    {
        return ch - '0';
    }
}

Answer 1

像这样改变main。

Scanner input = new Scanner(System.in);
String postfix = input.nextLine();
char[] charArray = postfix.replace(" ", "").toCharArray();
Node root = constructTree(charArray);
System.out.println("infix expression is");
System.out.println(root);

Answer 2

你为什么使用inorder()？root.toString()返回您想要的内容，"((1+2)*3)“

循环开始时可以跳过的空格：

    for (int i = 0; i < postfix.length; i++) {
        if (postfix[i] == ' ')
            continue;
        ...