Simple Regex matcher in C++

A regular expression is a set of pattern matching rules encoded in a string.Regular expression may match whole string or substring.

Here we will implement a regular expression matcher which will support . (dot), *, ^ and $.

Rules:

. (dot)	Dot matches any single character
*	Matches preceding character zero or more time

bool regexMatch(string regex, string str) {     if (regex.length() <= 0)     {         return true;     }          if (str.length() == 0 && regex.length() == 1 && regex[0] == '$')     {         return true;     }          if (str.length() > 0)     {         switch (regex[0])         {             case '^':                 return regexMatch(regex.substr(1, regex.length() - 1), str);             case '.':                 return regexMatch(regex.substr(1, regex.length() - 1), str.substr(1, str.length()-1));             case '*':                 {                     int itr = 0;                     while (itr < str.size())                     {                         if (regexMatch(regex.substr(1, regex.length() - 1), str.substr(itr, str.length()-itr)))                         {                             return true;                         }                         itr++;                     }                     return false;                 }             default:                 {                     int itr = 0;                     while (itr < regex.size())                     {                         if (regex[itr] == str[itr])                         {                             itr++;                         }                         else if (regex[itr] == '.' || regex[itr] == '*' || regex[itr] == '$' || regex[itr] == '^')                             return regexMatch(regex.substr(itr, regex.length() - itr), str.substr(itr, str.length()-itr));                         else                             return false;                     }                     return true;                 }                 return false;         }     }     return false; }

Check if the sub string exist in the target string : C++ code

Function below gives checks if the given sub string exists in the target string and prints the index of sub string.  

//Check if the given sub string exists in the string #include <iostream> using namespace std; bool CheckIfSubStringMatches(char * pStr, char * pSubStr) {     while( ('\0' != *pSubStr) && ('\0' != *pStr) )     {         if( *pSubStr != *pStr )             break;         pSubStr++;         pStr++;     }     if( '\0' == *pSubStr )     {         return true;     }     return false; } void SearchSubstring( char* pBigString, char* pSubstring) {     if( NULL == pBigString )     {         cout<< "Invalid string entered. None found" << endl;         return;     }     if( NULL == pSubstring )     {         cout << "Invalid sub string to search." << endl;         return;     }     if( strlen(pBigString) < strlen(pSubstring) )     {         cout << "None found " << endl;         return;     }     char * pStr = pBigString;     char * pSubStr = pSubstring;     int index = 0;     while( '\0' != *pStr )     {         if( *pStr == *pSubStr)         {             if( CheckIfSubStringMatches(++pStr, ++pSubStr) )             {                 cout << "Found SubString at Index = " << index << endl;                 return;             }             pSubStr = pSubstring;         }         else         {             pStr++;         }         index++;     }       cout << "None found " << endl; } int _tmain(int argc, _TCHAR* argv[]) {     char myStr[4][5] =    {{"This"},                          {"put."},                          {"xxxx"},                          {"g I "}                       };     char * string = "This is the string I wanted to input.";     for( int ctr = 0; ctr < 4; ctr++ )     {         SearchSubstring( string, myStr[ctr] );     }     return 0; }

The output of code above is given below

Found SubString at Index = 0 Found SubString at Index = 33 None found Found SubString at Index = 17

Move spaces from string to start of the string

We can move the spaces from given string at start easily, if we traverse the string from end. Whenever we encounter space while traversing the string from end just copy next character at the location of space and go on copying rest characters in the same fashion. This method take two iteration, one for finding out the end of string second to move the space.

Method MoveSpacesAtStart does the same. It first finds out the end of string and then starts searching spaces back words. This method maintains the character sequence except for the spaces, if we were allowed to alter the character sequence this can be done with single iteration as well.

//Method for moving all spaces from the string at start using only two iterations of the string #include <iostream> using namespace std; void MoveSpacesAtStart( char * inputString ) {     if ( NULL == inputString )     {         return;     }     cout << "Before : " << endl << inputString << endl;     char * end = inputString;     char * temp = NULL;     while( *(end + 1) != '\0' )     {         end++;     }     temp = end;     int spacecounter = 0;     while( end != inputString )     {         if( *end == ' ' )         {             spacecounter++;         }         else         {             *temp = *(temp - spacecounter);             temp--;         }         end--;     }     *temp = *(temp - spacecounter);     temp--;     while( temp != inputString)     {         *temp = ' ';         temp--;     }     *temp = ' ';     cout << "After: " << endl << inputString << endl << endl; } int _tmain(int argc, _TCHAR* argv[]) {     char myStr[4][38] =    {{"This is the string I wanted to input."},                          {"        the string I wanted to input."},                          {"This is the string.                  "},                          {"T i i s t e s r n  I w nt d to i p t."}                       };     for( int ctr = 0; ctr < 4; ctr++ )         MoveSpacesFromEnd( myStr[ctr] );       return 0; }

Out put of the above program is shown below

Before : This is the string I wanted to input. After:        ThisisthestringIwantedtoinput. Before :         the string I wanted to input. After:              thestringIwantedtoinput. Before : This is the string. After:                      Thisisthestring. Before : T i i s t e s r n  I w nt d to i p t. After:                  TiistesrnIwntdtoipt.

Code: Remove duplicate characters from string

Earlier we have seen code for checking for duplicates. We are now going to extend that code to remove the duplicates from the string.

void RemoveDuplicates(char* pchStringofDuplicates)

{

      if( NULL == pchStringofDuplicates || NULL == (pchStringofDuplicates +1))

            return ;

      char* pchPointToEnd, *pchPointToStart = pchStringofDuplicates++;

      pchPointToEnd = pchStringofDuplicates;

      while(*pchPointToEnd != NULL)

      {

            char* pchComparator = pchPointToStart;

            while(pchComparator != pchPointToEnd)

            {

                  if(*pchComparator == *pchPointToEnd)

                  {

                        break;

                  }

                  pchComparator++;

            }

            if(pchComparator == pchPointToEnd)

            {

                  *pchStringofDuplicates++ = *pchComparator;

            }

            pchPointToEnd++;

      }

      *pchStringofDuplicates = *pchPointToEnd;

}

Considering second character as tail(at first time), we will compare every character from start to tail, with tail. If we don't found match then we will add the tail in the same string. Do this till end of string.

Note: In C++ we are passing the char array to this function. If you try passing char* string you may get Access Violation error.  

Code: Make first character of string to upper case

Here the problem is just simple, we have to make uppercase to the first character of every input string. 


First Method: In this method we are going to consider that the string is having only ASCII characters. Then we will check first if the character fall between a to z, if yes then we will convert it to upper case by just adding the difference as shown below.

void MakeFirstCharUpper(char* pchInputString)
{
int aToInt = (int)'a';
int zToInt = (int)'z';
int AtoInt = (int)'A';


if(pchInputString == NULL)
return ;


int firstChar = (int)*pchInputString;
if(firstChar  <= zToInt && firstChar  >= aToInt )
{
*pchInputString = (char)(AtoInt + (firstChar  - aToInt));
}
}


Second Method: 
This will require when your string contains UNICODE characters. Here we will make copy of the original string, we will make that string to upper case, then we will only copy the first character of upper case string to original string.



void MakeFirstCharUpperUNICODEVersion(char* pchInputString)
{
if( NULL == pchInputString)
return;


if(strlen(pchInputString) == 1)
{
pchInputString = strupr(pchInputString);
return;
}


char* strPartI = new char(strlen(pchInputString));
strncpy(strPartI, pchInputString, strlen(pchInputString));


strPartI = strupr(strPartI);


*pchInputString = *strPartI;
}

Check if duplicate characters present in string

The problem we are discussing here is you have to return true if string specified contain at least one duplicate character. First we will be trying this without using the additional buffer. 


Idea is just simple: Try comparing each character from second character to end, with every character from start to that character. Don't try to compare from first character, otherwise  you will find the first match at the start itself.




bool IsDuplicatesCharPresent(char* pchStringToVerify)
{
if(pchStringToVerify == NULL)
return false;


char *pchStringStart = pchStringToVerify++;


while(pchStringToVerify != NULL)
{
char* pchComparator = pchStringStart;
while(pchComparator != pchStringToVerify)
{
if(*pchComparator == *pchStringToVerify)
{
return true;
}
pchComparator++;
}
pchStringToVerify++;
}
return false;
}

This can also be done using additional buffer, but your additional buffer may vary using as per the string character set. For example suppose if you are sure of having only ASCII characters then you will require buffer of size 256 length only, as shown below.



bool IsDuplicatesCharPresent(char* pchStringToVerify)
{
if(pchStringToVerify == NULL || (pchStringToVerify + 1) == NULL)
return false;
bool bArray[256] = {false};


while(*pchStringToVerify != NULL)
{
if(true == bArray[ (int)*pchStringToVerify ] )
return true;
else
bArray[ (int)*pchStringToVerify ] = true;
pchStringToVerify++;
}


return false;
}


This code is written considering the string is C style string, i.e. terminating with NULL. 

C++ Code for String Reverse

Here is a code for a program which does task of reversing the input string.

void StringReverse(char* pchStringToReverse)

{

        //if string is empty or having one character no need to reverse.

if(pchStringToReverse == NULL || (pcStringToReverse +1 ) == NULL) 

{

return;

}             

char* pchPointToLast = pchStringToReverse;

while(pchPointToLast)

{

pchPointToLast++;

}

pchPointToLast--;

while(pchStringToReverse < pchPointToLast)

{

     Char chTempStorage = *pchStringToReverse;

     *pchStringToReverse++  = *pchPointToLast;

     *pchPointToLast-- = chTempStorage; 

}

}

This code is written considering the string is C style string, i.e. terminating with NULL. If your string is not terminating with null then you might be need to replace the terminating conditions of while loops.

Unit Test Cases for above function:

1. Empty String.
2. String with only one character.
3. String with even number of characters.
4. String with odd number of characters.

There is one other way of doing this - its using recursion. But using recursion you can only print the string not store the string(I am not 100% sure about this).

void DisplayReverseString( char* pchStringToReverse)

{

if(*pchStringToReverse == NULL)

{

return;

}

else

{

DisplayReverseString(++pchStringToReverse);

cout<<*(pchStringToReverse -1 );

}

}

Please share your comments if any on the code or if you have any suggestions.