Computer Science Canada

java.lang.StackOverflowError?
Author:  a22asin [ Fri Oct 31, 2014 9:05 pm ]
Post subject:  java.lang.StackOverflowError?
Hi so im working on converting a program's function to use recursive instead of a while loop. Ive managed to quite a bit but just when i think i got it, i get a java.lang.StackOverflowError error and i cant figure out why im getting it. If i have done this right, it should separate the numbers and operations recursively and pass it to the next function to be evaluated. Unfortunately, i didnt to it right. Can someone please help me out as im a little new to recursions? Oh and the function is initially passed (string, 0,0,0).

code:

public static double evaluate(String s, int i,int j, int charIndex)   
        {
                double[] numbers = new double[3] ;
                Character[] operations = new Character[1];
                String next = "";
                int length = s.length();
                int numIndex = i;
                int operatIndex = j;

                if (charIndex < length)
                {
                        if (Character.isDigit(s.charAt(charIndex)) || s.charAt(charIndex) == '.' )
                        {
                                next += s.charAt(charIndex);
                        }
                        else
                        {
                               
                                first = s.charAt(charIndex);

                                switch (first)
                                {
                                case '+': // Addition
                                case '-': // Subtraction
                                case '*': // Multiplication
                                case '/': // Division
                                        numbers[numIndex]=(new Double(next));
                                        operations[operatIndex] = first;
                                        break;
                                case ')': // Right parenthesis
                                        evaluateStackTops(numbers, operations);
                                        break;
                                case '(': // Left parenthesis
                                        break;
                                default : // Illegal character
                                        throw new IllegalArgumentException("Illegal character");
                                }
                        }
                        evaluate(s, numIndex++, operatIndex++, charIndex++);
                }
                if (numbers.length != 3)
                        throw new IllegalArgumentException("Illegal input expression");
               
                return numbers[2];
        }
Author:  Tony [ Fri Oct 31, 2014 9:36 pm ]
Post subject:  RE:java.lang.StackOverflowError?
How deep does your recursion goes? Far enough to run out of stack space, suggesting that it's probably stuck in an infinite loop.

Pop-quiz. What's the result of
code:

int i = 2;
return i++  +  i;
Author:  a22asin [ Fri Oct 31, 2014 9:41 pm ]
Post subject:  Re: RE:java.lang.StackOverflowError?
Tony @ Fri Oct 31, 2014 9:36 pm wrote:
How deep does your recursion goes? Far enough to run out of stack space, suggesting that it's probably stuck in an infinite loop.

Pop-quiz. What's the result of
code:

int i = 2;
return i++  +  i;


it would return 6? what do u mean by how deep? Also, i cant seem to figure out why its going into an infinite loop. The charIndex would eventually == length of the string.
Author:  Tony [ Fri Oct 31, 2014 9:51 pm ]
Post subject:  RE:java.lang.StackOverflowError?
you've clearly didn't run the above code. It would return 5.

edit: understanding why it's a 5 instead of 6 should explain why it's not true that
Quote:

The charIndex would eventually == length of the string.


A good way to keep track of what's going on is to print the value of charIndex every time you enter the function -- that shows you both the progress being made (if any) and how often the function is called.
Author:  a22asin [ Fri Oct 31, 2014 9:54 pm ]
Post subject:  RE:java.lang.StackOverflowError?
no i didnt run it, seemed like a simple answer, i =2, i++ so i = 3 +i =6. but i was wrong. uhm.. wat does this have to do with the recursion though?
Author:  a22asin [ Fri Oct 31, 2014 9:56 pm ]
Post subject:  Re: RE:java.lang.StackOverflowError?
a22asin @ Fri Oct 31, 2014 9:54 pm wrote:
no i didnt run it, seemed like a simple answer,i forgot that +i is still 2 since it wasnt declared. but i was wrong. uhm.. wat does this have to do with the recursion though?
Author:  Tony [ Fri Oct 31, 2014 10:02 pm ]
Post subject:  RE:java.lang.StackOverflowError?
i++ is a post-increment and the way it works is that the return value is the current value of i, and contents of i are incremented after.

so in
code:

i = 2
i++ + i

it progresses as
code:

2 (i is set to 3) + i

and so
code:

2 + 3


there's ++i which would do what you would expect. Or just the simple i + 1 since you don't really need to assign anything back to the variable.
Author:  a22asin [ Fri Oct 31, 2014 10:12 pm ]
Post subject:  Re: RE:java.lang.StackOverflowError?
Tony @ Fri Oct 31, 2014 10:02 pm wrote:
i++ is a post-increment and the way it works is that the return value is the current value of i, and contents of i are incremented after.

so in
code:

i = 2
i++ + i

it progresses as
code:

2 (i is set to 3) + i

and so
code:

2 + 3


there's ++i which would do what you would expect. Or just the simple i + 1 since you don't really need to assign anything back to the variable.


oh ok i get it. So i changed the index++ to ++index for all of them and it works, but now im getting Error.java.lang.NumberFormatException with no source, not sure where im getting it. I have provided the code below for the whole. i tried to put some println to see where it goes wrong, but as soon as i enter the string, it gives me the error

code:

package q2;

// FILE: EvaluateDemonstration.java
// This program reads a reads and evaluates fully parenthesized arithmetic
// expressions.  The purpose is to illustrate a fundamental use of stacks.

import java.util.Stack;
import java.util.Scanner;
import java.util.regex.Pattern;

public class RecursiveEvaluateDemonstration
{

        public static void main(String[ ] args)
        {
                Scanner stdin = new Scanner(System.in);
                String expression;
                double answer;

                System.out.println("Please type an arithmetic expression made from");
                System.out.println("unsigned numbers and the operations + - * /.");
                System.out.println("The expression must be fully parenthesized.");

                do
                {
                        System.out.print("Your expression: ");
                        expression = stdin.nextLine( );
                        try
                        {
                                answer = evaluate(expression,0,0,0);
                                System.out.println("The value is " + answer);
                        }
                        catch (Exception e)
                        {
                                System.out.println("Error." + e.toString( ) + " Help");
                        }
                }
                while (query(stdin, "Another string?"));

                System.out.println("All numbers are interesting.");
        }


        public static boolean query(Scanner input, String prompt)
        {
                String answer;

                System.out.print(prompt + " [Y or N]: ");
                answer = input.nextLine( ).toUpperCase( );
                while (!answer.startsWith("Y") && !answer.startsWith("N"))
                {
                        System.out.print("Invalid response. Please type Y or N: ");
                        answer = input.nextLine( ).toUpperCase( );
                }

                return answer.startsWith("Y");
        }


        public static double evaluate(String s, int i,int j, int charIndex)   
        // Precondition: The string is a fully parenthesized arithmetic expression
        // formed from non-negative numbers, parentheses, and the four operations
        // +, -, *, and /.
        // Postcondition: The string has been evaluated and the value returned.
        // Exceptions: Can throw an NumberFormatException if the expression contains
        // characters other than digits, operations, parentheses and whitespace.
        // Can throw IllegalArgumentException if the input line is an
        // illegal expression, such as unbalanced parentheses or a division by zero.
        {
                double[] numbers = new double[3] ;
                Character[] operations = new Character[1];
                String next = "";
                int length = s.length();
                char first;
                int numIndex = i;
                int operatIndex = j;

                if (charIndex < length)
                {
                        if (Character.isDigit(s.charAt(charIndex)) || s.charAt(charIndex) == '.' )
                        {
                                next += s.charAt(charIndex);
                        }
                        else
                        {
                               
                                first = s.charAt(charIndex);

                                switch (first)
                                {
                                case '+': // Addition
                                case '-': // Subtraction
                                case '*': // Multiplication
                                case '/': // Division
                                        numbers[numIndex]=(new Double(next));
                                        System.out.println(numbers[numIndex]);
                                        operations[operatIndex] = first;
                                        break;
                                case ')': // Right parenthesis
                                        evaluateStackTops(numbers, operations);
                                        break;
                                case '(': // Left parenthesis
                                        break;
                                default : // Illegal character
                                        throw new IllegalArgumentException("Illegal character");
                                }
                        }
                        evaluate(s, ++numIndex, operatIndex+1, charIndex+1);
                }
                if (numbers.length != 3)
                        throw new IllegalArgumentException("Illegal input expression");
               
                return numbers[2];
        }


        public static void evaluateStackTops(double[] numbers, Character[] operations)     
        // Precondition: The top of the operations stack contains +, -, *, or /, and
        // the numbers stack contains at least two numbers.
        // Postcondition: The top two numbers have been popped from the numbers stack, and the
        // top operation has been popped from the operations stack. The two numbers have been
        // combined using the operation (with the second number popped as the left operand).
        // The result of the operation has then been pushed back onto the numbers stack.
        // Exceptions: Throws an IllegalArgumentException if the stacks are illegal or if the
        // operation results in a division by zero.
        {
                double operand1, operand2;

                // Check that the stacks have enough items, and get the two operands.
                if ((numbers.length < 2))
                        throw new IllegalArgumentException("Illegal expression");       
                operand2 = numbers[1];
                operand1 = numbers[0];

                // Carry out an action based on the operation on the top of the stack.
                switch (operations[0])
                {
                case '+': numbers[2] = (operand1 + operand2);
                break;
                case '-': numbers[2] = (operand1 - operand2);
                break;
                case '*': numbers[2]= (operand1 * operand2);
                break;
                case '/': // Note: A division by zero results in POSTIVE_INFINITY or
                        // NEGATIVE_INFINITY.
                        numbers[2] = (operand1 / operand2);
                        break;
                default : throw new IllegalArgumentException("Illegal operation");
                }
        }

        // These patterns are from Appendix B of Data Structures and Other Objects.
        // They may be used in hasNext and findInLine to read certain patterns
        // from a Scanner.
        public static final Pattern CHARACTER =
                        Pattern.compile("\\S.*?"); 
        public static final Pattern UNSIGNED_DOUBLE =
                        Pattern.compile("((\\d+\\.?\\d*)|(\\.\\d+))([Ee][-+]?\\d+)?.*?");
}
Author:  Tony [ Fri Oct 31, 2014 11:00 pm ]
Post subject:  RE:java.lang.StackOverflowError?
if you don't catch the exception, you get the full stack trace
Author:  a22asin [ Fri Oct 31, 2014 11:06 pm ]
Post subject:  Re: java.lang.StackOverflowError?
ok i ran the program without the try/catch and this is what i got:
code:

Exception in thread "main" java.lang.NumberFormatException: empty String
        at sun.misc.FloatingDecimal.readJavaFormatString(Unknown Source)
        at java.lang.Double.valueOf(Unknown Source)
        at java.lang.Double.<init>(Unknown Source)
        at q2.RecursiveEvaluateDemonstration.evaluate(RecursiveEvaluateDemonstration.java:94)
        at q2.RecursiveEvaluateDemonstration.evaluate(RecursiveEvaluateDemonstration.java:107)
        at q2.RecursiveEvaluateDemonstration.evaluate(RecursiveEvaluateDemonstration.java:107)
        at q2.RecursiveEvaluateDemonstration.main(RecursiveEvaluateDemonstration.java:29)


the first line at 94 refers to the line : numbers[numIndex]=(new Double(next));
but what i dont get is if the number im entering is an integer for example ( ex. (3+4) ), then why am i still getting this error.
Author:  a22asin [ Fri Oct 31, 2014 11:51 pm ]
Post subject:  Re: java.lang.StackOverflowError?
Ok so ive gone through and fixed majority of the errors. But now my answer is always coming out as 0.0. Im noticing that its not passing the case ')' or any of the math operations so it never passes the arrays to the stack evaluate. And again, I cant figure out why as the charIndex reaches the index of the ')'.

code:

public static double evaluate(String s, int i,int j, int charIndex)   
        // Precondition: The string is a fully parenthesized arithmetic expression
        // formed from non-negative numbers, parentheses, and the four operations
        // +, -, *, and /.
        // Postcondition: The string has been evaluated and the value returned.
        // Exceptions: Can throw an NumberFormatException if the expression contains
        // characters other than digits, operations, parentheses and whitespace.
        // Can throw IllegalArgumentException if the input line is an
        // illegal expression, such as unbalanced parentheses or a division by zero.
        {
                double[] numbers = new double[3] ;
                Character[] operations = new Character[1];
                String next = "";
                int length = s.length();
                char first;
                int numIndex = i;
                int operatIndex = j;

                if (charIndex < length)
                {
                        if (Character.isDigit(s.charAt(charIndex)) || s.charAt(charIndex) == '.' ){

                                boolean c = true;
                                while(c){
                                        if (Character.isDigit(s.charAt(charIndex)) || s.charAt(charIndex) == '.' ){
                                                next = ""+ next + "" + s.charAt(charIndex);
                                                charIndex++;
                                        }else{
                                                c = false;
                                        }
                                }
                                //System.out.println(charIndex);
                                numbers[numIndex]=(Double.parseDouble(next));
                        }else{

                                first = s.charAt(charIndex);
                               
                                switch (first)
                                {
                                case '+': // Addition
                                case '-': // Subtraction
                                case '*': // Multiplication
                                case '/': // Division
                                        operations[operatIndex] = first;
                                        break;
                                case ')': // Right parenthesis   <=skips this case even if the char is a ')'
                                        numbers[2] = evaluateStackTops(numbers, operations);
                                        break;
                                case '(': // Left parenthesis
                                        break;
                                default : // Illegal character
                                        throw new IllegalArgumentException("Illegal character");
                                }
                        }
                        evaluate(s, ++numIndex, operatIndex+1, charIndex+1);
                }

                if (numbers.length != 3)
                        throw new IllegalArgumentException("Illegal input expression");

                return numbers[2];
        }
Author:  C14 [ Sat Nov 01, 2014 8:24 am ]
Post subject:  RE:java.lang.StackOverflowError?
Have a look at what is being stored in your arrays.
For the code posted, and a simple test case of (2+2),
you numbers are not at positions 1 and 0.
Also your operator never gets stored.

You would be better off using and a stack where you can push and pop values like in your comments.
Then you no longer have to worry about array positions

Stack numbers = new Stack();
Stack operators = new Stack();
Author:  a22asin [ Sat Nov 01, 2014 10:33 am ]
Post subject:  RE:java.lang.StackOverflowError?
Quick question, the 1st char in a string is at what index? 0 right? Also, the original program uses stacks, but my assignment is to convert it to recursion instead of stacks; and this is the way i managed to get it to work. if you have a better way of making it a recursion, im open to suggestions as this is becoming quite a pain.
Author:  a22asin [ Sat Nov 01, 2014 10:49 am ]
Post subject:  Re: java.lang.StackOverflowError?
Ok, so i added some System.out to keep track at what char its at and its index and this is what i got with an input of (3+2):

code:

Please type an arithmetic expression made from
unsigned numbers and the operations + - * /.
The expression must be fully parenthesized.
Your expression: (3+2)
Char( Index: 0
Char3 Index: 1
Char2 Index: 3
The value is 0.0
Another string? [Y or N]:


So ya its skipping the + and the ) and i cant seem to figure out why, when i look at the code, everything seems fine to me. Sad

code:

public static double evaluate(String s, int i,int j, int charIndex)   
        // Precondition: The string is a fully parenthesized arithmetic expression
        // formed from non-negative numbers, parentheses, and the four operations
        // +, -, *, and /.
        // Postcondition: The string has been evaluated and the value returned.
        // Exceptions: Can throw an NumberFormatException if the expression contains
        // characters other than digits, operations, parentheses and whitespace.
        // Can throw IllegalArgumentException if the input line is an
        // illegal expression, such as unbalanced parentheses or a division by zero.
        {
                double[] numbers = new double[3] ;
                Character[] operations = new Character[1];
                String next = "";
                int length = s.length();
                char first;
                int numIndex = i;
                int operatIndex = j;

                if (charIndex < length)
                {
                        if (Character.isDigit(s.charAt(charIndex)) || s.charAt(charIndex) == '.' ){

                                boolean c = true;
                                while(c){
                                        if (Character.isDigit(s.charAt(charIndex)) || s.charAt(charIndex) == '.' ){
                                                next = ""+ next + "" + s.charAt(charIndex);
                                                System.out.println("Char" + next + " Index: " + charIndex);
                                                ++charIndex;
                                        }else{
                                                c = false;
                                        }
                                }
                                numbers[numIndex]=(Double.parseDouble(next));
                        }else{

                                first = s.charAt(charIndex);
                                System.out.println("Char" + first + " Index: " + charIndex);
                                switch (first)
                                {
                                case '+': // Addition
                                case '-': // Subtraction
                                case '*': // Multiplication
                                case '/': // Division
                                        operations[operatIndex] = first;
                                        System.out.println("operation");
                                        break;
                                case ')': // Right parenthesis
                                        System.out.println("end");
                                        numbers[2] = evaluateStackTops(numbers, operations);
                                        break;
                                case '(': // Left parenthesis
                                        break;
                                default : // Illegal character
                                        throw new IllegalArgumentException("Illegal character");
                                }
                        }
                        evaluate(s, ++numIndex, operatIndex+1, charIndex+1);
                }

                if (numbers.length != 3)
                        throw new IllegalArgumentException("Illegal input expression");

                return numbers[2];
        }
Author:  C14 [ Sat Nov 01, 2014 11:48 am ]
Post subject:  RE:java.lang.StackOverflowError?
evaluate(s, ++numIndex, operatIndex+1, charIndex+1);

Your numIndex should only increment after each number,
the operator index should increment after each operator.

The way you have it, they increment after each character regardless

Stacks can be used with recursion
Author:  a22asin [ Sat Nov 01, 2014 11:51 am ]
Post subject:  RE:java.lang.StackOverflowError?
oh i see, and im not allowed to use stacks, i have to replace stacks with recursion. The only thing is that numIndex and operIndex doesnt control what char to look at. My program keeps skipping the math operation char and the ) char no matter what expression i input. I modified the function again, this time, it recognises the ) but it skips the 2nd number and the operator.

code:

public static double evaluate(String s, int i, int charIndex)   
        {
                double[] numbers = new double[3] ;
                Character[] operations = new Character[1];
                String next = "";
                int length = s.length();
                char first;
                int numIndex = i;

                if (charIndex < length)
                {
                        System.out.println(" Index: " + charIndex);
                        if (Character.isDigit(s.charAt(charIndex)) || s.charAt(charIndex) == '.' ){
                                next = ""+ next + "" + s.charAt(charIndex);
                                System.out.println("Char" + next + " Index: " + charIndex);
                                if (Character.isDigit(s.charAt(++charIndex)) || s.charAt(++charIndex) == '.'){
                                        evaluate(s, numIndex, ++charIndex);
                                }
                                numbers[numIndex]=(Double.parseDouble(next));
                                ++numIndex;
                        }else{

                                first = s.charAt(charIndex);
                                System.out.println("Char" + first + " Index: " + charIndex);
                                switch (first)
                                {
                                case '+': // Addition
                                case '-': // Subtraction
                                case '*': // Multiplication
                                case '/': // Division
                                        operations[0] = first;
                                        System.out.println("operation");
                                        break;
                                case ')': // Right parenthesis
                                        System.out.println("end");
                                        numbers[2] = evaluateStackTops(numbers, operations);
                                        break;
                                case '(': // Left parenthesis
                                        break;
                                default : // Illegal character
                                        throw new IllegalArgumentException("Illegal character");
                                }
                        }
                        evaluate(s, numIndex, ++charIndex);
                }

                if (numbers.length != 3)
                        throw new IllegalArgumentException("Illegal input expression");

                return numbers[2];
        }

Author:  C14 [ Sat Nov 01, 2014 12:23 pm ]
Post subject:  RE:java.lang.StackOverflowError?
evaluate(s, numIndex, ++charIndex);

reduce it down to one recursive call. Recursion has an
'unwinding' effect.

The number is complete when you hit an operator or a right
parenthesis. That's when the number should be stored.

Usually loops are replaced with recursion.
Author:  a22asin [ Sat Nov 01, 2014 12:29 pm ]
Post subject:  Re: RE:java.lang.StackOverflowError?
C14 @ Sat Nov 01, 2014 12:23 pm wrote:
evaluate(s, numIndex, ++charIndex);

reduce it down to one recursive call. Recursion has an
'unwinding' effect.

The number is complete when you hit an operator or a right
parenthesis. That's when the number should be stored.
.


im not sure what u mean?

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy