Java RPN (Reverse Polish Notation) 中缀到后缀

Java RPN (Reverse Polish Notation) infix to postfix

提问by Margus

I am pretty sure, that stacks are used for building PRN and '(' are ignored, but it does not seem to be the case. For example:

我很确定，堆栈用于构建 PRN 和 '(' 被忽略，但似乎并非如此。例如：

• input 1:52+(1+2)*4-3
• input 2:52+((1+2)*4)-3
• input 3:(52+1+2)*4-3

• 输入1：52+(1+2)*4-3
• 输入2：52+((1+2)*4)-3
• 输入3：(52+1+2)*4-3

Input 1 and input 2 output should be the same, and input 1 and input 3 should differ.

输入 1 和输入 2 输出应该相同，输入 1 和输入 3 应该不同。

• output 1:52 1 2 + 4 3 - * +
• output 2:52 1 2 + 4 * 3 - +
• output 3:52 1 2 + 4 3 - * +

• 输出1：52 1 2 + 4 3 - * +
• 输出2：52 1 2 + 4 * 3 - +
• 输出3：52 1 2 + 4 3 - * +

    public static String Infix2(String input) {
        char[] in = input.toCharArray();
        Stack<Character> stack = new Stack<Character>();
        StringBuilder out = new StringBuilder();

        for (int i = 0; i < in.length; i++)
            switch (in[i]) {
            case '+':
            case '*':
            case '-':
                out.append(' ');
                stack.push(in[i]);
                break;
            case ' ':
            case '(':
                break;
            case ')':
                out.append(' ');
                out.append(stack.pop());
                break;
            default:
                out.append(in[i]);
                break;
            }

        while (!stack.isEmpty()) {
            out.append(' ');
            out.append(stack.pop());
        }

        return out.toString();
    }

Assuming that i want input 1 and 3 also to work, what approach should i use?

假设我希望输入 1 和 3 也能工作，我应该使用什么方法？

edit: After the changes '+','-','*' and '/' worked for given inputs.

编辑：更改后 '+'、'-'、'*' 和 '/' 适用于给定的输入。

public static String Infix2(String input) {
    if (input == null)
        return "";
    char[] in = input.toCharArray();
    Stack<Character> stack = new Stack<Character>();
    StringBuilder out = new StringBuilder();

    for (int i = 0; i < in.length; i++)
        switch (in[i]) {
        case '+':
        case '-':
            while (!stack.empty()
                    && (stack.peek() == '*' || stack.peek() == '/'))
                out.append(' ').append(stack.pop());
        case '*':
        case '/':
            out.append(' ');
        case '(':
            stack.push(in[i]);
        case ' ':
            break;
        case ')':
            while (!stack.empty() && stack.peek() != '(')
                out.append(' ').append(stack.pop());
            if (!stack.empty())
                stack.pop();
            break;
        default:
            out.append(in[i]);
            break;
        }

    while (!stack.isEmpty())
        out.append(' ').append(stack.pop());

    return out.toString();
}

采纳答案by brool

The algorithm is pretty simple (and here is a good explanation). Every operation has a binding weight, with + and - being the lowest. There are two rules:

该算法非常简单（这里有一个很好的解释）。每个操作都有一个绑定权重，+ 和 - 是最低的。有两个规则：

• print out numbers immediately
• never put a lighter item on a heavier item
• left parentheses go on the stack
• right parentheses pop off the stack until you hit a left parentheses, and then remove the left parentheses

• 立即打印出数字
• 切勿将较轻的物品放在较重的物品上
• 左括号进入堆栈
• 右括号从堆栈中弹出，直到遇到左括号，然后删除左括号

Given your first example, 52+(1+2)*4-3, here is the stack:

鉴于您的第一个示例，52+(1+2)*4-3，这是堆栈：

 52+          => +
 52+(         => + (
 52+(1+       => + ( + 
 52+(1+2)     => +       //right parentheses popped +
 52+(1+2)*4   => + * 
 52+(1+2)*4-3 => + -     //can't put - on top of *, so pop off *
 ... and then pop the stack until it's empty.

Replacing your switch loop with the following (closest analog to what you had) will give correct answers for your three examples. In a real parser you would give each operator a weight and generalize the pop mechanism.

用以下（与您所拥有的最接近的模拟）替换您的开关回路将为您的三个示例提供正确的答案。在真正的解析器中，您将给每个运算符一个权重并概括弹出机制。

for (int i = 0; i < in.length; i++)
        switch (in[i]) {
        case '+':
        case '-':
            while (!stack.empty() && (stack.peek() == '*' || stack.peek() == '/')) {
                out.append(' ');
                out.append(stack.pop());
            }
            out.append(' ');
            stack.push(in[i]);
            break;
        case '*':
        case '/':
            out.append(' ');
            stack.push(in[i]);
            break;
        case '(':
            stack.push(in[i]);
            break;
        case ')':
            while (!stack.empty() && stack.peek() != '(') {
                out.append(' ');
                out.append(stack.pop());
            }
            stack.pop();
            break;
        default:
            out.append(in[i]);
            break;
        }

回答by Andreas Dolk

Not an exact answer to the specific question but something I'd recommend for developing these kinds of algorithms: have a look at test driven devlopment (TDD). In brief: write a couple of unit tests - for example with JUnit - for the infix2 method, where you feed the method with test patterns (expressions) and test, if infix2 produces the right output.

不是特定问题的确切答案，而是我建议开发此类算法的内容：查看测试驱动开发 (TDD)。简而言之：为 infix2 方法编写几个单元测试 - 例如使用 JUnit - 为方法提供测试模式（表达式）和测试，如果 infix2 产生正确的输出。

Start with easy ones, like

从简单的开始，比如

assertequals("1", "1"); // positive number
assertequals("-1", "-1"); // negative number
assertequals("1+1", "1 1 +"); // simple addition
assertequals(" 1 + 1 ", "1 1 +"); // simple addition with whitechars
assertequals(" 1 + +1 ", "1 -1 +"); // simple addition with pos. number & whitechars
assertequals(" 1 + -1 ", "1 -1 +"); // simple addition with neg. number & whitechars
assertequals("(1+1)", "1 1 +"); // simple addition with brackets

and don't forget illegal expressions like

并且不要忘记像这样的非法表达

String[] illegalExpressions = {null, "", " ", "1 +", "1 + 1)"};

The test cases for you examples should be

示例的测试用例应该是

assertequals("52+(1+2)*4-3", "52 1 2 + 4 * 3 -");
assertequals("52+((1+2)*4)-3", "52 1 2 + 4 * 3 -");
assertequals("(52+1+2)*4-3", "52 1 + 2 + 4 * 3 -");