java - 表达式树 : Postfix to 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

为什么使用 inorder()？ root.toString() 返回的正是您想要的，“((1+2)*3)”

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

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