代码之家 › 专栏 › 技术社区 › Margus

JavaRPN(反向波兰符号)中缀到后缀

algorithm java

Margus · 技术社区 · 15 年前

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

2 回复 | 直到 10 年前

brool 15 年前

算法非常简单(而且 here is a good explanation )每个操作都有一个绑定权重,其中+和-是最低的。有两条规则:

立即打印出号码
不要将较轻的物品放在较重的物品上。
左括号位于堆栈上
右括号从堆栈中弹出,直到碰到左括号,然后删除左括号。

给出第一个例子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.

将开关回路替换为以下(与您所拥有的最接近的模拟回路)将为您的三个示例提供正确的答案。在一个真正的解析器中,您将给每个操作符一个权重并概括pop机制。

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

Andreas Dolk 15 年前

不是对特定问题的确切答案,但我建议开发这些算法:看看测试驱动开发(TDD)。简而言之:为infix2方法编写两个单元测试(例如,使用junit),如果infix2生成正确的输出,则使用测试模式(表达式)和测试来填充该方法。

从简单的开始,比如

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

别忘了像这样的非法表达

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

您示例的测试用例应该是

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 -");