Java RPN(反向波兰表示法)中缀到后缀

Question

我很确定,堆栈用于构建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();
}

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