java - 如何避免 ArrayIndexOutOfbounds 异常？

Question

我正在尝试使用堆栈解决中缀表达式，但我的程序似乎抛出 ArrayIndexOutOfBoundsException。

您能指导我如何解决代码中的错误吗？

程序类

public class CS6084BTolani {

    public static String evaluateInfix(String exps)
    {
        exps = exps.replaceAll(" ", "");//removing white spaces
        System.out.println(exps);

        StackADT<Double> values = new StackADT<Double>(exps.length());//Stack for Operands
        StackADT<String> ops = new StackADT<String>(exps.length());//for operators


        StringTokenizer tokens = new StringTokenizer(exps, "()^*/+-", true);//to seperate all the operands and operators 

        while(tokens.hasMoreTokens())
        {
            String tkn = tokens.nextToken();

            if(tkn.equals("(")) 
            {
                ops.push(tkn);
                System.out.println("ADDING to ops : "+ops.peek());
            } 
            else if(tkn.matches("\\d+\\.\\d+")||tkn.matches("\\d+"))
            {

                values.push(Double.valueOf(tkn));
                System.out.println("ADDING to values : "+values.peek());
            }
            else if (tkn.equals("^") || tkn.equals("*") || tkn.equals("/") || tkn.equals("+") || tkn.equals("-"))
            {
                while (!ops.isEmpty() && hasPrecedence(tkn, ops.peek()))
                  values.push(applyOp(ops.pop(), values.pop(), values.pop()));
              System.out.println("ADDING to values: "+values.peek());

                // Push current token to 'ops'.
                ops.push(tkn);
                System.out.println("ADDING to ops: "+ops.peek());
            }
            else if(tkn.equals(")"))
            {
                while (!(ops.peek()).equals("("))
                {
                  values.push(applyOp(ops.pop(), values.pop(), values.pop()));
                  System.out.println("ADDING to values: "+values.peek());
                }
                ops.pop();
            }


        }

        while (!ops.isEmpty())
            values.push(applyOp(ops.pop(), values.pop(), values.pop()));

        // Top of 'values' contains result, return it
        return String.valueOf(values.pop());
    }

    public static boolean hasPrecedence(String op1, String op2)
    {
        if (op2 == "(" || op2 == "(")
            return false;
        if ( (op1 == "^" ) && (op2 == "+" || op2 == "-"))
            return false;
        if ( (op1 == "^" ) && (op2 == "*" || op2 == "/"))
            return false;
        if ( (op1 == "*" || op1 == "/") && (op2 == "+" || op2 == "-"))
            return false;
        else
            return true;
    }

    public static double applyOp(String op, double b, double a)
    {
        switch (op)
        {
        case "^":
            return Math.pow(a,b);
        case "+":
            return a + b;
        case "-":
            return a - b;
        case "*":
            return a * b;
        case "/":
            if (b == 0)
                throw new
                UnsupportedOperationException("Cannot divide by zero");
            return a / b;
        }
        return 0;
    }

    public static void main(String a[]) throws Exception
    {
        //Input ip = new Input("inputData4B.txt");
        String expOne = "(100.0 + 2.3)";//ip.getFirstString();
        System.out.println("Answer: "+evaluateInfix(expOne));
        //String expTwo = ip.getSecondString();
        //System.out.println("Answer: "+evaluateInfix(expTwo));
        //String expThree = ip.getThirdString();
        //System.out.println("Answer: "+evaluateInfix(expThree));
        //String expFour = ip.getFourthString();
        //System.out.println("Answer: "+evaluateInfix(expFour));
    }
}

堆栈类

class StackADT<T extends Object> {

    private int stackSize;
    private T[] stackArr;
    private int top;


    public StackADT(int size) 
    {
        stackSize = size;
        stackArr = (T[]) new Object[stackSize];
        top = -1;
    }
    public void push(T element){

        stackArr[++top] = element;
    }
    public T pop()  
    {
        if(isEmpty())
        {
            System.out.println("Stack is isEmpty.");
        }
        T element = stackArr[top--];
        return element;
    }
    public T peek() 
    {
        return stackArr[top];
    }

    public boolean isEmpty() 
    {
        return (top == -1);
    }    
}

运行时是这样的:

java CS6084BTolani

(100.0+2.3)


ADDING to ops : (

ADDING to values : 100.0

Stack is isEmpty.

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1

at StackADT.pop(CS6084BTolani.java:139)

at CS6084BTolani.evaluateInfix(CS6084BTolani.java:38)

at CS6084BTolani.main(CS6084BTolani.java:102)

Answer 1

分析

这似乎是一个逻辑错误(概念错误？)。

尝试使用标记顺序评估表达式。当下一个操作 token 可用时，将应用操作，但在弹出值之前不会检查值堆栈大小是否大于或等于执行(解释)操作所需的值的数量。这就是为什么最后打印的消息是 Stack isEmpty.。

一般说明

算法——中缀表达式求值算法。

如果目标是学习如何设计算法，那么尝试自己设计。否则，请使用其描述来学习算法，例如，来自 this source .

在更新当前实现之前，请尝试了解它有什么问题:将其与设计或描述的版本进行比较。之后，更新实现或创建一个新的实现(如果需要进行大量更改)。

解决方案

目前，我发现操作优先级处理存在问题。请考虑以下操作处理:

else if (tkn.equals("^") || tkn.equals("*") || tkn.equals("/") || tkn.equals("+") || tkn.equals("-")) {
    if (!ops.isEmpty() && !hasPrecedence(tkn, ops.peek())) {
        values.push(applyOp(ops.pop(), values.pop(), values.pop()));
        System.out.println("ADDING to values: " + values.peek());
    }
    else {
        // Push current token to 'ops'.
        ops.push(tkn);
        System.out.println("ADDING to ops: " + ops.peek());
    }
}