Problem of the Day
A new programming or logic puzzle every Mon-Fri

Comments:

• James - 10 years, 4 months ago

  Admittedly not my best work. Does not recursively parse nested parenthesis, and due to the static variables, it is not possible for the caller to implement that behavior him/herself. I should really pass a parse state structure into parse_parens(), but then I'd have to write psudo-constructor/destructor functions... This implementation diverges from the problem statement in that it does not return an array of strings. It must be called multiple times to achieve the desired effect. I wasn't sure what the problem meant by "two stets" of parenthesis, so I ignored the word "two". Text between mismatched parenthesis is ignored (one parenthesis does not make a set).

  #include <stdio.h>
  #include <string.h>
  
  // Use 'parse_parens()' like 'strtok()'.
  // Input string is mutated by this function.
  char * parse_parens( char * input )
  {
     static char * start_ptr  = NULL;
     char *        token      = NULL;
     char *        next;
     int           skip_paren = 0;
  
     if ( input != NULL )
     {
        start_ptr = input;
     }
  
     // Advance past the first open-paren.
     token = strchr( start_ptr, '(' );
     if ( token == NULL )
     {
        goto EXIT;
     }
  
     token++;
  
     // Advance to the next paren.
     next = strpbrk( token, "()" );
     ;
     while ( next != NULL )
     {
        // Handle nested parens.
        if ( *next == '(' )
        {
           skip_paren++;
           next++;
        }
        else if ( *next == ')' )
        {
           if ( skip_paren > 0 )
           {
              skip_paren--;
              next++;
           }
           else
           {
              *next = '\0';
              break; // Success.
           }
        }
  
        next = strpbrk( next, "()" );
     }
  
     // Detect mismatched parens.
     if ( next == NULL )
     {
        token = NULL;
        goto EXIT;
     }
  
     // Advance past the last close-paren.
     start_ptr = next + 1;
  
  EXIT:
     if ( token == NULL )
     {
        start_ptr = NULL;
     }
  
     return token;
  }
  
  int main( void )
  {
     char * token;
     char   str[] = "This(is(a)test)string."
                    "(More(words(for)performing)the)test."
                    "Hmm(),(what(happens(on)mismatch)?";
  
     token = parse_parens( str );
     while ( token != NULL )
     {
        printf( "%s\n", token );
        token = parse_parens( NULL );
     }
  
     return 0;
  }
  

  reply permalink

• Nick Krichevsky - 10 years, 4 months ago

  def between(s):
      indexes = {}
      i = 0
      j = len(s)-1
      while i!=-1:
          i = s.find('(',i)
          j = s.find(')',j)
          indexes[i]=j if j!=-1 else None
          i+=1 if i!=-1 else 0
          j-=1 if j!=-1 else 0    
      if -1 in indexes:
          del indexes[-1]
      substrings = []
      for item in indexes:
          substrings.append(s[item+1:indexes[item]])
      return substrings
  
  print between('((hello))')
  

  reply permalink

• Anonymous - 10 years, 4 months ago

  def text_between(text):
      open_indexes = [] # Used as stack, index of (s
      for ind, ch in enumerate(text):
          if ch == '(':
              open_indexes.append(ind)
          elif ch == ')' and open_indexes: # Skip )s without a matching (
              opened = open_indexes.pop() + 1 # +1 to cut out (
              yield text[opened:ind]
  

  Should correctly match nested parentheses, probably the simplest it can go

  reply permalink