how to avoid ArrayIndexOutOfbounds Exception?

Question

I am trying to solve a infix expression using stacks and my program seems to throw an ArrayIndexOutOfBoundsException.

Can you guide me on how to solve my bug in the code?

Program class

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

Stack class

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

On running it is like this:

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)

I can't see an obvious cause but it looks as if `values.push(applyOp(ops.pop(), values.pop(), values.pop()));` is getting called before `2.3` gets pushed onto value stack. You could make the second `ADDING to values` print statement different to the first so you can tell the events apart, and move it into the `while` loop. — John D, Oct 01 '16 at 19:58
@JohnD I am sorry, I did not understand which while loop are you talking about. can you elaborate? — Mayur Tolani, Oct 01 '16 at 20:03
Related question: [How to evaluate an infix expression in just one scan using stacks?](http://stackoverflow.com/questions/13421424/how-to-evaluate-an-infix-expression-in-just-one-scan-using-stacks). — Sergey Vyacheslavovich Brunov, Oct 01 '16 at 22:17

score 0 · Answer 1 · answered Oct 01 '16 at 20:07

0

This is not an answer but a suggestion to make the program easier to debug - it won't fit in a comment :)

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 calculations to values: "+values.peek());
        }

answered Oct 01 '16 at 20:07

John D

1,627
1
11
10

turns out the code breaks before reaching this point. That Print statement doesn't get executed. @johnD – Mayur Tolani Oct 01 '16 at 20:11
Looks like a job for the debugger - stepping through each statement! – John D Oct 01 '16 at 20:14

Sergey Vyacheslavovich Brunov · Accepted Answer · 2016-10-01T22:16:57.837

0

Analysis

It seems to be a logical error (conceptual mistake?).

There is the attempt to evaluate an expression sequentially using tokens. When the next operation token is available, the operation is being applied, but there is no check that the value stack size is greater or equal to the number of values required to perform (interpret) the operation before popping the values. This is why the last printed message is Stack is isEmpty..

General note

The algorithm — the infix expressions evaluation algorithm.

If the goal is to learn how to design the algorithm, then try to design it by yourself. Otherwise, learn the algorithm using its description, for example, from this source.

Before updating the current implementation, please try to understand what is wrong with it: compare it with the designed or described version. Right after that, update the implementation or create a new one if a lot of changes are required.

Solution

Currently, I see a problem with operation precedence handling. Please consider the following operation handling:

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

edited Oct 01 '16 at 22:16

answered Oct 01 '16 at 21:15

Sergey Vyacheslavovich Brunov

17,291
7
48
81

1

thankyou so much! Tthe whole time i was checking everything else but the precedence. i had gone through that link that you just provided, that link is actually my professor's, who is teaching me this subject. tysm! – Mayur Tolani Oct 01 '16 at 22:36
@MayurTolani, you are welcome! Glad it has helped. Amazing coincidence! – Sergey Vyacheslavovich Brunov Oct 01 '16 at 23:17
@MayurTolani, if this is it, please consider accepting the answer. – Sergey Vyacheslavovich Brunov Oct 02 '16 at 22:48
1

the help is really appreciated. but the code is giving wrong answers. I guess, some other logical error has come up. The infix expression is being evaluated, but it isn't following the order properly – Mayur Tolani Oct 03 '16 at 18:11
@MayurTolani, the original problem has been solved. But, as suggested previously, the entire implementation and the `hasPrecedence()` method, in particular, should be revised, shouldn't it? – Sergey Vyacheslavovich Brunov Oct 03 '16 at 18:16
1

yes The original problem has been solved. I will give your answer as the correct answer and I will update the code with proper working code when i get it right. – Mayur Tolani Oct 03 '16 at 18:20
@MayurTolani, thank you! According to the «Meta Stack Overflow» ([Updating questions after they've been answered to give a follow-up](http://meta.stackoverflow.com/questions/306573/updating-questions-after-theyve-been-answered-to-give-a-follow-up)), such an update is not required because the original problem has been solved. – Sergey Vyacheslavovich Brunov Oct 03 '16 at 18:29