java - 后缀到中缀

Question

我正在尝试将后缀转换为中缀。我有一些代码，但我无法修复它。我可能缺少一个条件。或者我的结构不太正确。 另外，由于我是 Java 新手，我可能需要一些有关“Stack<Character>”的帮助。

public static String postfixToInfix(String postfix) {
    Stack<Character> stack = new Stack();
    Stack<Character> backup = new Stack();
    StringBuilder infix = new StringBuilder(postfix.length());
    infix.append('(');
    for (int i = 0; i < postfix.length(); i++) {
        if (!isOperator(postfix.charAt(i))) {
            stack.push(postfix.charAt(i));
        } else {
            if (stack.size() == 1 ) {                               //stack is 1
                backup.push(postfix.charAt(i));
            }
            if (stack.size() == 0 && backup.size()%5 == 0) {        //stack is 0
                stack.push(backup.pop());
                stack.push(backup.pop());
                stack.push(backup.pop());
                stack.push(backup.pop());
                stack.push(backup.pop());
                stack.push(postfix.charAt(i));
            }
            if (stack.size() >= 2) {                                //stack is > 1
                char arg2 = stack.pop();
                char arg1 = stack.pop();
                backup.push(')');
                backup.push(arg2);
                backup.push(postfix.charAt(i));
                backup.push(arg1);
                backup.push('(');
            }
        }
    }

    while (!backup.empty()) { //only size 3
        stack.push(backup.pop());
    }
    while (!stack.empty()) { //only size 3
        backup.push(stack.pop());
    }
    while (!backup.isEmpty()) {
        infix.append(backup.pop());
    }
    infix.append(')');
    return infix.toString();
}

private static boolean isOperator(char c) {
        return c == '+' || c == '-' || c == '*' || c == '/' || c == '^' || c == '(' || c == ')';
    }

public static void main(String[] args) {
        String infix1 = "(3-(7*2))";
        String postfix1 = "372*-";
        String infix2 = "((7+1)*((3-6)*(5-2)))";
        String postfix2 = "71+36-52-**";

        System.out.println("                postfix1: " + postfix1);
        s = postfixToInfix(postfix1);
        System.out.println("postfixToInfix(postfix1): " + s);
        if (s.equals(infix1)) {
            System.out.println("                       Korrekt!");
        } else {
            System.out.println("                       Nicht korrekt!");
        }
        System.out.println();

        System.out.println("                postfix2: " + postfix2);
        s = postfixToInfix(postfix2);
        System.out.println("postfixToInfix(postfix2): " + s);
        if (s.equals(infix2)) {
            System.out.println("                       Korrekt!");
        } else {
            System.out.println("                       Nicht korrekt!");
        }
        System.out.println();
    }
}

输出

                postfix1: 372*-
postfixToInfix(postfix1): (3-(7*2))
                       Korrekt!

                postfix2: 71+36-52-**
postfixToInfix(postfix2): ((5(-*2)()**)(3-6)(7+1))
                       Nicht korrekt!


Process finished with exit code 0

Answer 1

您可以使用字符串来简化过程，而不是将括号和所有内容作为堆栈中的单独条目处理:

private static boolean isOperator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
}

public static String postfixToInfix(String postfix) {
    Stack<String> s = new Stack<String>();
    for (char c : postfix.toCharArray()) {
        if (isOperator(c)) {
            String temp = s.pop();
            s.push('(' + s.pop() + c + temp + ')');
        } else {
            s.push(String.valueOf(c));
        }
    }
    return s.pop();
}