-----------------------------------

a22asin

Fri Oct 31, 2014 9:05 pm


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];
	}
[/code]


-----------------------------------

Tony

Fri Oct 31, 2014 9:36 pm


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;
[/code]


-----------------------------------

a22asin

Fri Oct 31, 2014 9:41 pm


Re: 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


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.


-----------------------------------

Tony

Fri Oct 31, 2014 9:51 pm


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

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.


-----------------------------------

a22asin

Fri Oct 31, 2014 9:54 pm


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?


-----------------------------------

a22asin

Fri Oct 31, 2014 9:56 pm


Re: RE:java.lang.StackOverflowError?

-----------------------------------

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?


-----------------------------------

Tony

Fri Oct 31, 2014 10:02 pm


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
++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.


-----------------------------------

a22asin

Fri Oct 31, 2014 10:12 pm


Re: 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
++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+)?.*?");
}
[/code]


-----------------------------------

Tony

Fri Oct 31, 2014 11:00 pm


RE:java.lang.StackOverflowError?

-----------------------------------

if you don't catch the exception, you get the full stack trace


-----------------------------------

a22asin

Fri Oct 31, 2014 11:06 pm


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.(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)
[/code]

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.


-----------------------------------

a22asin

Fri Oct 31, 2014 11:51 pm


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