java - java 中的 bc 实用程序，在某些情况下会失败

Question

我正在尝试用 java 编写简单的 bc 实用程序。我的程序在大多数情况下都运行良好，但对于表达式 4+4*3-3-2-1/3 却失败了。基本上是连续的 - 运营商。不确定我是否涵盖了所有边缘情况。任何让它变得更好的建议都会非常有帮助。谢谢

//ENUM for operations allowed.
private enum Operators {
    ADD         (1, "+"),
    SUBTRACT   (1, "-"),
    MULTIPLY    (2, "*"),
    DIVIDE      (2, "/");

    String operator;
    // Operator priority
    int weight;
    Operators(int w, String o) {
        this.operator = o;
        this.weight = w;
    }

    public String getOperator() {
        return operator;
    }

    public int getWeight() {
        return weight;
    }
}
// Stack and Queue to convert expression to postfix
LinkedList<String> resultQueue = new LinkedList<String>();
Stack<Operators> operatorStack = new Stack<Operators>();
//Stack to evaluate postfix expression
Stack<Integer> evalStack = new Stack<Integer>();

public int eval(String exp) {
    char[] expChar = exp.toCharArray();
    int i = 0;
    StringBuilder sb = new StringBuilder();
    while (i < expChar.length){
        if (expChar[i] >= '0' && expChar[i] <= '9') {
            sb.append(expChar[i]);

            if (i == expChar.length - 1) {
                resultQueue.add(sb.toString());
                while (!operatorStack.isEmpty()){
                    resultQueue.add(operatorStack.pop().getOperator());
                }
            }
        } else if (expChar[i] == '+' || expChar[i] == '-' || expChar[i] == '/' || expChar[i] == '*'){
            if (sb.length() > 0) {
                resultQueue.add(sb.toString());
                sb = new StringBuilder();
            }
                pushOperator(expChar[i]);
        } else
        return 0;
        i++;
    }
    for (String r : resultQueue){
        if (r.charAt(0) > '0' && r.charAt(0) < '9'){
            evalStack.push(Integer.valueOf(r));
        }else {
            try {
                int op2 = evalStack.pop();
                int op1 = evalStack.pop();
                if (r.charAt(0) == '+')
                    evalStack.push(Integer.valueOf(op1+op2));
                else if (r.charAt(0) == '-')
                    evalStack.push(Integer.valueOf(op1-op2));
                else if (r.charAt(0) == '/')
                    evalStack.push(Integer.valueOf(op1/op2));
                else if (r.charAt(0) == '*')
                    evalStack.push(Integer.valueOf(op1*op2));
            } catch (Exception e){
                System.out.println("Parse Error");
                return 0;
            }
        }
    }
    int result=0;
    try{
        result = evalStack.pop();
    }catch (Exception e){
        System.out.println("Parse Error");
    }

    return result;
}

private void pushOperator(char c) {
    Operators val = getOperator(c);
    if (operatorStack.isEmpty() || val.getWeight() >= operatorStack.peek().getWeight()){
        operatorStack.push(val);
    } else {
        while (!operatorStack.isEmpty() && val.getWeight() <= operatorStack.peek().getWeight()){
            resultQueue.add(operatorStack.pop().getOperator());
        }
        operatorStack.push(val);
    }
}

private Operators getOperator(char c) {
    for (Operators o: Operators.values()){
        if (o.getOperator().equals(String.valueOf(c)))
            return o;
    }
    throw new IllegalArgumentException("Operator not supported");
}

public static void main(String[] args) {

    BC bc = new BC();
    System.out.println("Please enter expression: ");
    Scanner scn = new Scanner(System.in);
    String exp = scn.nextLine();
    //remove white spaces
    exp = exp.replaceAll(" ", "");
    System.out.println("Result: " + bc.eval(exp));
    scn.close();
}

Answer 1

问题在于，对于连续的减法运算，您计算的方向是错误的。您从右到左计算，而您需要从左到右计算。

如果您在堆栈上有操作符 12 3 2 0 - - - 您的计算效率很高

12 - (3 - (2 - 0)) = 11

正确的应该是

12 - (3 + 2 + 0) = 7

一种可能的修复方法是。在开始计算之前，您需要将堆栈上的操作数更改为 12 3 2 0++ -。

请参阅此代码段，它可以在计算循环之前执行。

// your code
...
    }
    i++;
}

for (i = 0; i < resultQueue.size() - 1; i++) {
    if ("-".equals(resultQueue.get(i)) && "-".equals(resultQueue.get(i+1))) {
        resultQueue.set(i, "+");
    }
}

// your code
for (String r : resultQueue) {
    if (r.charAt(0) > '0' && r.charAt(0) < '9') {
...