Results 1 to 7 of 7
  1. #1
    Spinz is offline Member
    Join Date
    Jul 2013
    Posts
    6
    Rep Power
    0

    Default Recursion algorithm correct?

    HI, I would like to know if I am correctly implementing this recursion algorithm for matching the different types of brackets ({ [
    I provide you with the code below. I appreciate your help!

    Java Code:
     public void recursiveMatch (FileReader src)
             throws MatchFail 
      {
       
    	/*Algorithm in general
    	 * read next character
    	 * If find an open bracket, if of the three types return 1; 0 otherwise.
    	 * 	Through a counter, save locations of each open bracket.
    	 * 
    	 * -> For every open bracket found, call recursive method
    	 * 
    	 * read up to matching closed bracket
    	 * 		Matching: if open == closed [compare value in stack, dependent on counter] return 1, 0 otherwise
    	 * 		counter -> smallest values first
    	 */
    	  
    	  
    	 	//Definitions for different types of brackets:
    		final char openbracket1 = '(';
    		final char openbracket2 = '{';
    		final char openbracket3 = '[';
    		
    		final char closedbracket1 = ')';
    		final char closedbracket2 = '}';
    		final char closedbracket3 = ']';
    		
    		
    		//create stack for brackets using ArrayDeque
    		ArrayDeque<Character> bracket = new ArrayDeque<Character>();
    
    		//create a stack for indeces depicting bracket location within textfile
    		ArrayDeque<Integer> index = new ArrayDeque<Integer>();
    		
    		//definition for character read from file
    		int charAsInt=0;
    		
    		//create counter for index stack
    		int counter = 0;
    
    		while (charAsInt!=EOF){
    			
    			//character read from file (character by character)
    			 charAsInt = getOneChar(src) ; //retieves only one character from source code
    			
    			//just to know what the counter value is at 
    			System.out.println(counter);
    			
    			//text character is read in its character form, not by its index
    			char presentChar = (char) charAsInt ;
    			System.out.println("current char: "+presentChar);
    			
    			//go to the next slot to store the index found from open brackets
    			counter++;
    		
    			if (presentChar==openbracket1||(presentChar==openbracket2)||(presentChar==openbracket3))
    			{
    				bracket.push(presentChar);
    				index.push(counter);
    				counter++;
    				
    				System.out.print("counter is:" +counter);
    			}
    				recurs();
    			
    		}
    	}
    
    private void recurs() {
    	// TODO Auto-generated method stub
    	//how will it call itself?
    	
    	recurs();
    	
    }
    }

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,525
    Blog Entries
    7
    Rep Power
    20

    Default Re: Recursion algorithm correct?

    If you keep a stack of positions of the left-brackets, there's no need for recursion; i.e. when you read a right-bracket simpy check that stack and pop the position or generate an error condition.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    Spinz is offline Member
    Join Date
    Jul 2013
    Posts
    6
    Rep Power
    0

    Default Re: Recursion algorithm correct?

    Thank you for your reply! I was able to use your suggestion and works great, I was just wondering how can recursion be implemented then? I would really like to know, thanks again! :)

  4. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,525
    Blog Entries
    7
    Rep Power
    20

    Default Re: Recursion algorithm correct?

    Quote Originally Posted by Spinz View Post
    Thank you for your reply! I was able to use your suggestion and works great, I was just wondering how can recursion be implemented then? I would really like to know, thanks again! :)
    Suppose there exists a method read() that returns an int representing the next char read or -1 when no more characters could be read; the following (more or less pseudo) code is a recursive implementation:

    Java Code:
    boolean parse(int stop) {
       int current;
       while ((current= read()) != stop) {
          if (current == '(' && !parse(')')) return false;
          else if (current == '{' && !parse('}')) return false;
          else if (current == '[' && !parse(']')) return false;
       }
       return true;
    }
    That method also uses a stack depth equal to the number of left parentheses in the character sequence; the while loop simply iterates over the characters between matching parentheses. You call that method as parse(-1) (parse until the end of stream is reached).

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  5. #5
    Spinz is offline Member
    Join Date
    Jul 2013
    Posts
    6
    Rep Power
    0

    Default Re: Recursion algorithm correct?

    For example, this is what I tried to do for recursion... what do you think?

    Java Code:
    public class MatchingBrackets {
    
     public void recursiveMatch (FileReader src)
             throws MatchFail 
      {
       
    	/*Algorithm in general
    	 * read next character
    	 * If find an open bracket, if of the three types return 1; 0 otherwise.
    	 * 	Through a counter, save locations of each open bracket.
    	 * 
    	 * -> For every open bracket found, call recursive method
    	 * 
    	 * read up to matching closed bracket
    	 * 		Matching: if open == closed [compare value in stack, dependent on counter] return 1, 0 otherwise
    	 * 		counter -> smallest values first
    	 */
    	  
    	  
    	 	//Definitions for different types of brackets:
    		final char openbracket1 = '(';
    		final char openbracket2 = '{';
    		final char openbracket3 = '[';
    		
    		final char closedbracket1 = ')';
    		final char closedbracket2 = '}';
    		final char closedbracket3 = ']';
    		
    		
    		//create stack for brackets using ArrayDeque
    		ArrayDeque<Character> bracket = new ArrayDeque<Character>();
    
    		//create a stack for indeces depicting bracket location within textfile
    		ArrayDeque<Integer> index = new ArrayDeque<Integer>();
    		
    		//definition for character read from file
    		int charAsInt=0;
    		
    		//create counter for index stack
    		int counter = 0;
    
    		while (charAsInt!=EOF){
    			
    			//character read from file (character by character)
    			 charAsInt = getOneChar(src) ; //retieves only one character from source code
    			
    			//just to know what the counter value is at 
    			System.out.println(counter);
    			
    			//text character is read in its character form, not by its index
    			char presentChar = (char) charAsInt ;
    			System.out.println("current char: "+presentChar);
    			
    			//go to the next slot to store the index found from open brackets
    			counter++;
    		
    			if (presentChar==openbracket1||(presentChar==openbracket2)||(presentChar==openbracket3))
    			{
    				bracket.push(presentChar);
    				index.push(counter);
    				counter++;
    			}	
    			else if ((presentChar ==  closedbracket1)||(presentChar == closedbracket2)||(presentChar == closedbracket3))
    					{
    				//pop available opening bracket from the stack
    						char myChar = bracket.pop();
    						recursmatch();
    					}
    		}
    	}
    //recursive method but I am not sure how to use the values obtained above in here...help!
    
    private void recursmatch() {
    	// TODO Auto-generated method stub
    
    	//obtain values of index and counter
    	index.recursiveMatch();
    	counter.recursiveMatch();
    	
    	//obtain opening bracket from stack
    	myChar.recursiveMatch();
    	
    	//let the present char be the closing bracket read from the text file
    	presentChar.recursiveMatch();
    	
    	if (presentChar == myChar)
    	{
    		//call the method again to check matches with previous opening brackets
    		recursmatch();
    	}
    	else 	{
    				System.out.println("A mismatch occurred for the opening bracket at location "
    					+ index +"and for the closing bracket at location"+ counter);
    			} throw new MatchFail();	
    }
    }

  6. #6
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,525
    Blog Entries
    7
    Rep Power
    20

    Default Re: Recursion algorithm correct?

    Quote Originally Posted by Spinz View Post
    For example, this is what I tried to do for recursion... what do you think?
    Too much code for me (I'm sitting in bright sunlight at the moment and I can hardly read the code ;-) If you want a recursive method you don't need an explicit stack.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  7. #7
    Spinz is offline Member
    Join Date
    Jul 2013
    Posts
    6
    Rep Power
    0

    Default Re: Recursion algorithm correct?

    Hahaha it's midnight here so since the 'night' is young i'll keep on trying out your suggestion! Thanks for the hints!

Similar Threads

  1. A recursion issue with quickSort algorithm
    By patishi in forum New To Java
    Replies: 2
    Last Post: 02-12-2013, 06:48 AM
  2. can u tell me w/c one is correct?
    By akocnivek in forum New To Java
    Replies: 4
    Last Post: 10-21-2012, 10:03 AM
  3. Please correct this JSP code
    By rajesh4851 in forum New To Java
    Replies: 5
    Last Post: 06-13-2011, 12:12 PM
  4. Please help - can't seem to correct this...
    By jmjbreezin in forum New To Java
    Replies: 7
    Last Post: 05-09-2011, 01:39 PM
  5. recursion and tail-recursion differences
    By OptimusPrime in forum New To Java
    Replies: 2
    Last Post: 12-28-2009, 06:26 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •