逆波蘭給出錯誤的答案

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

這裏是一個簡潔的解決方案做對飛的計算：

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首先應該轉換綴形式爲後綴形式。爲此，您可以使用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; 
    } 
} 

和操作類：

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's solution for Shunting Yard Implementation