# Recursion algorithm correct?

• 07-20-2013, 09:20 AM
Spinz
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!

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();         } }```
• 07-20-2013, 10:12 AM
JosAH
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
• 07-21-2013, 08:25 AM
Spinz
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! :)
• 07-21-2013, 09:25 AM
JosAH
Re: Recursion algorithm correct?
Quote:

Originally Posted by Spinz
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:

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
• 07-21-2013, 09:29 AM
Spinz
Re: Recursion algorithm correct?
For example, this is what I tried to do for recursion... what do you think?

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();        } }```
• 07-21-2013, 09:31 AM
JosAH
Re: Recursion algorithm correct?
Quote:

Originally Posted by Spinz
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
• 07-21-2013, 09:40 AM
Spinz
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!