反向抛光给出错误答案

Question

我需要制作一个接受中缀表达式并使用 rpn 对其求值的计算器。

Java代码：

public RpnCalculator() {

}


public float eval(float arg1, float arg2, String operator) {
    switch (operator) {
        case PLUS:
            return arg1 + arg2;
        case MINUS:
            return arg2 - arg1;
        case MULTIPLICATION:
            return arg1 * arg2;
        case DIVISION:
            return arg2 / arg1;
        default:
            return 0;
    }
}

public String evaluateInfixExpression(String expression) {
    Stack<String> operators = new Stack<>();
    String[] args = expression.split(SPACE);
    Stack<String> values = new Stack<>();

    for (String arg : args) {
        if (isANumber(arg)) {
            values.push(arg);
            continue;
        }
        if (operators.isEmpty()) {
            operators.push(arg);
        } else if (precedence(arg) <= precedence(operators.peek())) {
            float result = eval(Float.parseFloat(values.pop()), Float.parseFloat(values.pop()), operators.pop());
            values.push(String.valueOf(result));
            operators.push(arg);
        } else if (precedence(arg) > precedence(operators.peek())) {
            operators.push(arg);
        }
    }


    while (!operators.isEmpty()) {
        float result = eval(Float.parseFloat(values.pop()), Float.parseFloat(values.pop()), operators.pop());
        values.push(String.valueOf(result));
    }

    return expression;
}

public int precedence(String operator){
    if (operator.equals(PLUS) || operator.equals(MINUS)){
        return 1;
    }
    return 2;

}

public boolean isANumber(String number) {
    if (number.matches("-?\d+")) {
        return true;
    }
    return false;
}

}

它运行良好，除了有时会给出错误的答案... 在我看来，我正在遵循调车场算法原则，但正如您所看到的，我实际上并没有将中缀转换为后缀，但我尝试在旅途中评估参数，也许这是个问题。

例如表达式 -2 + 6 * 8 / 3 * 18 - 33 / 3 - 11 计算结果为 286 而不是 264。应该有一些我没能注意到的错误，已经两天了所以请帮助我。此外，我在堆栈上阅读了很多关于 RPN 的帖子，但似乎每个人都有不同的问题，所以我没有找到适合我的案例的答案。

谢谢。

Answer 1

我不是 RPN 专家，但我注意到您正在按从右到左的顺序评估参数，因此在评估乘法和除法之后，您会得到以下结果：

operators = + - -
values = -2 288 11 11

然后你做（从右到左的顺序）：

11 - 11 = 0     // would expect -22 here
288 - 0 = 288
-2 + 288 = 286

你的结果不正确。

如果您按从左到右的顺序计算，您将得到：

-2 + 288 = 286
286 - 11 = 275
276 - 11 = 264

所以我稍微修改了你的代码：

public String evaluateInfixExpression(String expression) {
    Deque<String> operators = new LinkedList<>();
    String[] args = expression.split(SPACE);
    Deque<String> values = new LinkedList<>();

    for (String arg : args) {
        if (isANumber(arg)) {
            values.push(arg);
            continue;
        }
        if (operators.isEmpty()) {
            operators.push(arg);
        } else if (precedence(arg) <= precedence(operators.peek())) {
            float result = eval(Float.parseFloat(values.pop()), Float.parseFloat(values.pop()), operators.pop());
            values.push(String.valueOf(result));
            operators.push(arg);
        } else if (precedence(arg) > precedence(operators.peek())) {
            operators.push(arg);
        }
    }

    while (!operators.isEmpty()) {
        String v1 = values.removeLast();
        String v2 = values.removeLast();
        float result = eval(Float.parseFloat(v2), Float.parseFloat(v1), operators.removeLast());
        values.addLast(String.valueOf(result));
    }
    return expression;
}

Answer 2

对于RPN，首先你应该将中缀形式转换为后缀形式。为此，您可以使用 Dijkstra 的 Shunting-yard algorithm。

此算法的示例实现：

public class ShuntingYard {
    private static boolean isHigerPrec(String op, String sub) {
        return (ops.containsKey(sub) && ops.get(sub).precedence >= ops.get(op).precedence);
    }

    public static Stack<String> postfix(String infix) {
        Stack<String> output = new Stack<>();
        Deque<String> stack  = new LinkedList<>();

        for (String token : infix.split("\s")) {
            if (ops.containsKey(token)) {
                while ( ! stack.isEmpty() && isHigerPrec(token, stack.peek()))
                    output.push(stack.pop());
                    stack.push(token);
                }  else {
                    output.push(token);
                }
        }

        while ( ! stack.isEmpty()) 
            output.push(stack.pop());
        return reverse(output);
    }

    private static Stack<String> reverse(Stack<String> original) {
        Stack<String> reverse = new Stack<>();
        while(!original.isEmpty()) reverse.push(original.pop());
        return reverse;
   }
}

和操作class：

public enum Operator {
    ADD(1), SUBTRACT(1), MULTIPLY(2), DIVIDE(2);
    final int precedence;
    Operator(int p) { precedence = p; }

    public static Map<String, Operator> ops = new HashMap<String, Operator>() {{
        put("+", Operator.ADD);
        put("-", Operator.SUBTRACT);
        put("*", Operator.MULTIPLY);
        put("/", Operator.DIVIDE);
    }};

    public static Operator fromString(String str){
        return ops.get(str);
    }
}

你的class终于修改了：

public class RpnCalculator {
    private static Float eval(float arg1, float arg2, Operator operator) {
        switch (operator) {
            case ADD:
                return arg1 + arg2;
            case SUBTRACT:
                return arg2 - arg1;
            case MULTIPLY:
                return arg1 * arg2;
            case DIVIDE:
                return arg2 / arg1;
            default:
                throw new IllegalArgumentException("Operator not supported: " + operator);
        }
    }

    public static Float evaluateInfixExpression(String expression) {
        Stack<String> stack = ShuntingYard.postfix(expression);
        Stack<Float> result = new Stack<>();
        while(!stack.isEmpty()){
            String nextElement = stack.pop();
            if(isANumber(nextElement)){
                result.push(new Float(nextElement));
            } else {
                result.push(eval(result.pop(), result.pop(), Operator.fromString(nextElement)));
            }
        }
        return result.pop();
    }

    private static boolean isANumber(String number) {
        return number.matches("-?\d+");
    }
}

资源：

Edd Mann's solution for Shunting Yard Implementation

Answer 3

这里有一个简洁的解决方案，可以即时进行计算：

public class RpnCalculator {
    public static Float evaluateInfixExpression(String inflixExpression) {
        Stack<Float> operands = new Stack<>();
        Stack<Operator> operators = new Stack<>();

        for (String token : inflixExpression.split("\s")) {
            if (isOperator(token)) {
                while (!operators.isEmpty() && operators.peek().hasHigherPrecedenceThan(token))
                    operands.add(eval(operands.pop(), operands.pop(), operators.pop()));
                operators.push(fromString(token));
            } else {
                operands.add(new Float(token));
            }
        }

        while (!operators.isEmpty())
            operands.add(eval(operands.pop(), operands.pop(), operators.pop()));

        return operands.pop();
    }

    private static Float eval(float arg2, float arg1, Operator operator) {
        switch (operator) {
            case ADD:
                return arg1 + arg2;
            case SUBTRACT:
                return arg1 - arg2;
            case MULTIPLY:
                return arg1 * arg2;
            case DIVIDE:
                return arg1 / arg2;
            default:
                throw new IllegalArgumentException("Operator not supported: " + operator);
        }
    }
}

和 Operator class:

public enum Operator {
    ADD(1), SUBTRACT(1), MULTIPLY(2), DIVIDE(2);
    final int precedence;
    Operator(int p) { precedence = p; }

    private static Map<String, Operator> ops = new HashMap<String, Operator>() {{
        put("+", Operator.ADD);
        put("-", Operator.SUBTRACT);
        put("*", Operator.MULTIPLY);
        put("/", Operator.DIVIDE);
    }};

    public static Operator fromString(String token){
        return ops.get(token);
    }

    public static boolean isOperator(String token) {
        return ops.containsKey(token);
    }

    public boolean hasHigherPrecedenceThan(String token) {
        return isOperator(token) && this.precedence >= fromString(token).precedence;
    }
}

反向抛光给出错误答案

reversed polish giving wrong answer

java

rpn

calculator