Discussions & Sparks » Crack the Interview » Technical and Coding Interview Questions

Regular Expressions based pattern matching in a String

(2 posts)

  1. Spark
    Moderator

    Question:

    Write a program to perform a regular expressions based pattern matching in a String.

    Posted 1 year ago #

  2. Spark
    Moderator

    This may not be the perfect solution but still a good one. Here's the code:


    // function definition
    BOOL isMatch(CHAR* str, CHAR* pattern, int& len);

    // Handles '*' in the pattern
    BOOL HandleAsterisk(CHAR* str, CHAR* pattern, int& len)
    {
    if((*(pattern + 1) == '') || (*str == ''))// || (*(str + 1) == ''))
    {
    return TRUE;
    }
    else if(*(str + 1) == '')
    {
    len = len + 1;
    return TRUE;
    }
    if(*(str + 1) == *(pattern + 1))
    {
    len = len + 1;
    return isMatch((str + 1), (pattern + 1), len);
    }
    len = len + 1;
    return isMatch((str + 1), (pattern), len);
    }

    // if pattern matches
    BOOL isMatch(CHAR* str, CHAR* pattern, int& len)
    {
    if(*str == '')
    {
    if(*pattern == '')
    {
    return TRUE;
    }
    else
    {
    return FALSE;
    }
    }
    else if(*pattern == '')
    {
    return TRUE;
    }

    if(*pattern == '*')
    {
    len = len + 1 ;
    return HandleAsterisk(str + 1, pattern, len);
    }
    else if((*pattern == '?') || (*pattern == *str))
    {
    len = len + 1;
    return isMatch(str + 1, pattern + 1, len);
    }
    return FALSE;
    }

    // pattern matching
    void PatternMatching(CHAR* str, CHAR* pattern)
    {
    int iLenStrLen = strlen(str);
    int iLenPattern = strlen(pattern);
    int count = 0;
    printf("Pattern: %s", pattern);
    for(int i = 0; i < iLenStrLen; i++)
    {
    int len = 0;
    if(isMatch((str + i), pattern, len))
    {
    count++;
    printf("\nMatch %d: Len %d. String found: ", count, len);
    for(int j = 0; j < len; j++)
    {
    printf("%c", *(str + j + i));
    }
    printf("\nin String %s\n", str);
    }
    }
    }

    // main function
    int _tmain(int argc, _TCHAR* argv[])
    {
    char *s = "cabcdaaaxcdzd";
    char *p = "c?a*d";
    PatternMatching(s, p);

    return 0;
    }

    Posted 1 year ago #

RSS feed for this topic

Reply

You must log in to post.