javastackprefixevaluator

getting java.lang.OutOfMemory error with my prefix expression evaluator


Below i have the code for evaluating a prefix expression. I first read the expression into inputArray which allows me to read from right to left, then use evaluationArray to do the operations. I get out of memory error on this line: evaluationStack.push(number); I have no idea why this is happening. any help would be greatly appreciated.

import java.util.*;

public class PrefixEvaluator 
{
    //evaluates a prefix expression
    public static int evaluate(String input)
    {
        int number, leftOperand, rightOperand, result;
        char operator;
        String inputToken = null;

        //create input stack
        Stack<String> inputStack = new Stack<String>();
        //create an integer stack
        Stack<Integer> evaluationStack = new Stack<Integer>();


        //create string tokenizer containing input string
        StringTokenizer tokenizer = new StringTokenizer(input);

        //read string into a stack
        while (tokenizer.hasMoreTokens())
        {
            inputToken = tokenizer.nextToken(); //get next token
                inputStack.push(inputToken);   //push token     
        }


        while (inputStack.isEmpty() != true)
        {      
           //System.out.println(inputStack.pop());

            if (isNumber(inputToken))
            {
                number = Integer.parseInt(inputToken);
                evaluationStack.push(number);
            }
            else                         //if token is operator
            {
                operator = inputToken.charAt(0);   //get operator
                rightOperand = evaluationStack.pop();
                leftOperand  = evaluationStack.pop();
                result = evaluation(operator, leftOperand, rightOperand);
                evaluationStack.push(result);
            }
        }
        return evaluationStack.pop();
    }

    //tests whether token is a number
    private static boolean isNumber(String token)
    {
        char first = token.charAt(0);
        if (Character.isDigit(first))
            return true;
        else
            return false;

    }

    //perform an operation on two operands
    private static int evaluation(char operator, int leftOperand, int rightOperand)
    {
        if (operator == '+')
            return leftOperand + rightOperand;
        else if (operator == '-')
            return leftOperand - rightOperand;
        else if (operator == '*')
            return leftOperand * rightOperand;
        else if (operator == '%')
            return leftOperand % rightOperand;
        else
            return leftOperand / rightOperand;

    }


    public static void main (String [] args)
    {
        evaluate("* 4 - 165 235");
    }

}

Solution

  • If you step through your code in your debugger you will see that this code is an infinite loop.

        while (inputStack.isEmpty() != true)
        {      
           //System.out.println(inputStack.pop());
    
            if (isNumber(inputToken))
            {
                number = Integer.parseInt(inputToken);
                evaluationStack.push(number);
    

    You keep testing inputToken and adding it to a stack but you never change it so it runs until you run out of memory.

    Perhaps you intended to have this at the start of the loop

           inputToken = inputStack.pop();
    

    If you also add

    System.out.println(evaluate("* 4 - 165 235"));
    

    it prints

    280