倒波兰式给出错误答案

Question

我需要制作一个计算器，它使用infix表达式并使用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;
}

}

而且效果很好，只是有时会给出错误的答案.对我来说，我似乎遵循了调车场算法的原则，但正如你所看到的，我实际上并没有将infix转换为后缀，但是我尝试在执行过程中评估参数，也许这是一个问题。

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

谢谢。

Answer 1

下面是一个简洁的解决方案，可以动态地进行计算：

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类：

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

Answer 2

我不是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 3

对于RPN，首先您应该将infix表单转换为后缀表单。为此，您可以使用来自Dijkstra的调车码算法。

此算法的示例实现如下：

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

而手术课：

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

最后，您的类修改了：

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调车场的解决方案