Regular expression matching in a string

roverphoenix 0 182 Views

Regular expression pattern match in a string, I only checked with * as wild card, other wild card characters are easy implement but I havent done that.

any problems you can email me @

platform - Unix/Linux, havent tested in windows, should'nt be a problem unless some standard header files are missing.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int index;

int main()
{
  char *reg_str,*str;
  int flag = 0;
  int reg_index = 0;
  int i = 0;
  int reg_len = 0;
  int *arr;
  int arr_count = 0;
  int reg_flag = 0;
  int Find_Match(char c,int flag, char *str,int *arr, int *arr_count);

  reg_str = (char *)malloc(100);
  str = (char *)malloc(100);
  arr = (int *)malloc(100 *sizeof(int));
  index = 0;
  printf("Enter the regular expression ..\n");
  gets(reg_str);
  printf("\nEnter the string ..\n");
  gets(str);
  reg_len = strlen(reg_str);
  
  for(i = 0;i < reg_len;i++)
    {
      if(reg_str[i] == '*')
	{
	  //reg_index++;
	  flag = 1;
	  free(arr);
	  arr_count = 0;
	}
      else
	{
	  if(Find_Match(reg_str[i],flag,str,arr,&arr_count) == 0)
	    {
	      printf("pattern not found ...\n");
	      reg_flag = 1;
	      break;
	    }
	}
    }
  if(reg_flag == 0)
    printf("reg exp pattern found in the string ..\n");
  return 0;
}

int Find_Match(char c,int flag, char *str,int *arr, int *arr_count)
{
  int i = 0;
  int counter = 0;
  int arr_index = 0;

  if(flag == 0)
    {
      if(str[index] == c)
	{
	  index++;
	  return 1;
	}
      else 
	{
	  return 0;
	}
    }

  else
    {
      if(*arr_count == 0)
	{
	  for(i = index;str[i] != '\0';i++)
	    {
	      if(str[i] == c)
		{
		  arr[*arr_count] = i;
		  *arr_count = *arr_count + 1;
		  if(counter == 0)
		    {
		      index++;
		      counter++;
		    }
		}
	    }
	}
      else
	{
	  for(i = 0;i < *arr_count;i++)
	    {
	      if(arr[i] == -1)
		continue;
	      arr_index = arr[i] + 1;
	      if(str[arr_index] == c)
	      {
		arr[i] = arr_index;
		if(counter == 0)
	        {
		  index = arr_index + 1;
		  counter++;
		}
	      }
	      else
	      {
		arr[i] = -1;
	      }
	   }
	}
    }
   if(counter == 0)
     return 0;
   else
     return 1;
}

Dani AI

Generated

Good starter, — a simple '*' matcher is useful as a learning exercise, but the implementation shown has a few safety and correctness problems that make it unreliable in real use. is right to flag the input routine; there are also use-after-free, indexing, and semantic issues that should be fixed before treating the program as a working pattern matcher.

The main issues to address:

  • Freeing the match-index array inside the loop (then continuing to use the pointer) creates undefined behavior. Either reuse the allocated array (reset its count and overwrite entries) or free and immediately reallocate before any further use.
  • The global variable named index couples state across calls and can be shadowed by system symbols; make position state local (e.g. size_t pos) and pass it between functions.
  • No checks on malloc/realloc return values and no bounds checks when indexing str or arr can lead to crashes.
  • The current handling of * is ambiguous (does it apply to the previous token, the next one, or mean "match anything"?). Decide the regex semantics up front or use a standard engine.

Practical fixes (examples):

  • Replace unsafe input with fgets and strip the trailing newline:

    char buf[100];
if (!fgets(buf, sizeof buf, stdin)) /* handle EOF/error */;
size_t n = strlen(buf);
if (n && buf[n-1] == '\n') buf[n-1] = '\0';

  • Allocate with checked calls (arr = malloc(N * sizeof *arr)), avoid freeing arr inside the main loop (use arr_count = 0;), and use size_t for indices.

For production or full regex semantics, prefer existing libraries: POSIX regcomp/regexec or fnmatch for glob-style patterns. For a simple wildcard engine that supports * and ?, a dynamic-programming (DP) matcher (string vs. pattern table) is clearer and less error-prone than ad-hoc state arrays. Run the code with Valgrind or address sanitizer to catch memory errors, and test edge cases (empty pattern, leading/trailing *, consecutive *, and very long inputs).

Member Avatar for ~s.o.s~
~s.o.s~ 2,560 Failure as a human

Dont use "gets( )" for accepting string input from user -- It is a bad programming practice and the function itself is flawed as it doesnt check for buffer overflows. Use [search]fgets( )[/search] instead.

Avoid use of globals if possible -- there is no condition where the program cant be done without using globals. Using globals prevents your algo or program being used as a part of a larger program.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Edit Preview