Java RPN（反向波兰符号）后缀

小编典典

Java RPN（反向波兰符号）后缀

algorithm

我很确定，堆栈用于构建PRN，而’（’会被忽略，但事实并非如此。例如：

输入1： 52+（1 + 2）* 4-3
输入 2：52 +（（（1 + 2）* 4）-3
输入3： （52 + 1 + 2）* 4-3

输入1和输入2的输出应该相同，输入1和输入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();
}

假设我还希望输入1和输入3也起作用，我应该使用哪种方法？

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

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();
}

阅读 293

2020-07-28

共1个答案

小编典典

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

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

给您第一个示例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.

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

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;
        }

2020-07-28