5
\$\begingroup\$

I'm trying to optimize my solution to the following question:

given a regular expression with chars and special char '*', (star which is a joker we can replace with any string), and a string, write a program which determines if the regular expression can represent that string or not. for example: "a'*b" can represent "aaaacbbbb" , in contrast "a'*b'*c" cant represent "aaaabcccccccccb"

I solved the problem and inserted the code below, I want to optimize either space or time, and if possible to make it more readable or shorter.

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


int compareHelper(char *s, char *regex, int star);

int compareStrings(char *s, char *r);

int main()
{
    printf("%d\n", compareStrings("aaaacbbb", "a*b"));
    printf("%d\n", compareStrings("aaaabccccccccb", "a*b*c"));
    return 0;

}

//aaaaacbbb
//a*b

int compareStrings(char *s, char *r)
{
    return compareHelper(s, r, 0);

}

int compareHelper(char *s, char *regex, int star)
{
    if (*s == '\0' && *regex == '\0')
    {
        return 1;
    } else if (*regex == '*')
    {
        return compareHelper(s, regex + 1, 1); // star is seen hence will be set to true.
    } else
    {
        if (!star)
        {
            if (*s != *regex)
            { // star was not seen and they differ in char
                return 0;
            } else
            {
                return compareHelper(s + 1, regex + 1, star);
            }

        } else
        {
            while (*s && *s != *regex)
            {
                s++;
            }
            if (*s == '\0') return 0;
            else
            {
                return compareHelper(s + 1, regex + 1, 0) | compareHelper(s + 1, regex, 1);
            }
        }
    }
}

\$\endgroup\$
1
  • \$\begingroup\$ Looks like someone doesn't know what regular expressions are. Where is that from? And what's up with those single-quotes in "a'*b'*c"? \$\endgroup\$ Nov 19 '20 at 21:26
0
\$\begingroup\$

This (non recursive) solution has more lines, but simpler ones. The break out of the inner loop was not so easy to find -- first I had no else, and more continue and braces...

#include <stdio.h>

/* Return 0 if matches. Otherwise some high number */
int glob_str(char *glob, char *str) {

    int starred = 0, i;
    int jperm   = 0, j;

    for (i = 0; glob[i] != '\0'; i++) {
        
        if (glob[i] == '*') {
            starred = 1;
            continue;
        }
        if (starred) {  
            for (j = jperm;;) {
                if (str[j] == '\0') 
                    return i + 1000;
                if (str[j++] == glob[i]) 
                    break;          
            }
            jperm = j;  
            starred = 0;
        } 
        else  
            if (glob[i] != str[jperm++]) 
                return i + 2000;
    }
    /* Check if str is unfinished - wildcard vs. regex */
    if (!starred && str[jperm])
        return 99;
    /* Match */
    return 0;
}

int main() {
    char *string = "abccccec";
    char *globex = "abc*ec";
    int diff = glob_str(globex, string);
    printf("diff: %d (tried globex=%s on string=%s)\n", diff, globex, string);
    return 0;
}

The recursive version looks very short, like 4 lines. But if you format these lines into more regular chunks, it amounts to about the same.

bool match(char *first, char *second)
{
    if (*first == '\0' && *second == '\0')
        return true;

    if (*first == '*' && *(first + 1) != '\0' && *second == '\0')
        return false;

    if (*first == *second)
        return match(
            first + 1, second + 1);

    if (*first == '*')
        return 
            match( first + 1, second) ||
            match( first, second + 1);

    return false;
}

Compact version

With pointers and while.

After some rearrangements. The g and s variables are not necassary. But now it is clear where the pointers are incremented (str++ in two places). The first version makes a fuss about j and jperm -- I realize now that both pointers/indexes advance only forward.

int glob_str(char *glob, char *str) {

    int starred = 0;
    char g, s;

    while ((g = *glob++) != '\0') {

        if (g == '*') {
            starred = 1;
            continue;
        }
        if (starred) {
            while ((s = *str++) != g)
                if (s == '\0')
                    return 1;
            starred = 0;
        }
        else
            if (*str++ != g)
                return 2;
    }
    if (!starred && *str)
        return 99;      
    return 0;
}
\$\endgroup\$
1
  • \$\begingroup\$ You have presented alternative solutions, but haven't reviewed the code. Please explain your reasoning (how your solution works and why it is better than the original) so that the author and other readers can learn from your thought process. \$\endgroup\$ Nov 20 '20 at 13:28
4
\$\begingroup\$

The code you wrote can be improved in lots of places. I'll go through it from top to bottom.

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

Perfect until now. The #include lines from the C standard library should be in alphabetic order. I cannot say whether you did this intentionally or not since there's a 50-50 chance. :)

int compareHelper(char *s, char *regex, int star);

This function should be declared as static, since it is local to this file. To do this, replace the int compareHelper with static int compareHelper.

The compare in the function name is wrong. Typically, to compare two things, they have to be of the same or at least a compatible type. The technical type here is char *, but on a more abstract level, s is an arbitrary string while regex is a string with some constraints. Instead of compare, this function should be called match.

The type of the string parameters should be const char * instead of char * since this function does not modify the characters of these strings.

The type of the parameter star should be bool instead of int. To get this type, you have to add #include <stdbool.h> along with the other #include lines.

The name of the parameter regex is wrong. The word regex means regular expression, and this is a fixed term with a precise definition. Your patterns are not regular expressions, therefore the parameter name confuses the reader. Better call it pattern.

int compareStrings(char *s, char *r);

Again, the compare should rather be match, the parameter types should get an additional const, and the return type should be bool instead of int.

int main()
{
    printf("%d\n", compareStrings("aaaacbbb", "a*b"));
    printf("%d\n", compareStrings("aaaabccccccccb", "a*b*c"));
    return 0;
}

The empty parentheses () in the function declaration of main mean that the function can take any number of parameters. In C, this is only allowed for legacy code from 1990 and earlier. In modern code, write (void) instead to clearly say that there must be no parameters.

//aaaaacbbb
//a*b

This is the beginning of documentation, which is a good idea. To be useful for other readers, you should write in whole sentences though, for example:

// See if the string s matches the pattern p.
// In the pattern, '*' matches an arbitrarily long sequence of arbitrary characters.
int compareHelper(char *s, char *regex, int star)
{
    if (*s == '\0' && *regex == '\0')
    {
        return 1;
    } else if (*regex == '*')

After the return 1, the else is unnecessary. I would write the code like this instead:

    if (*s == '\0' && *regex == '\0') {
        return 1;
    }

    if (*regex == '*') {
        ...

This way, your code has one topic per paragraph. The empty line between the topics clearly marks a pointer where the reader may stop reading and take a deep breath, before starting to read the next paragraph.

The rest of the code looks fine, except for this line:

return compareHelper(s + 1, regex + 1, 0) | compareHelper(s + 1, regex, 1);

The operator | means a logical or, and it always evaluates both operands. This means that compareHelper is called twice, even if the left-hand side already evaluates to true. This is not necessary. To only evaluate the necessary parts of the condition, replace the | operator with ||.

All in all, the code is not too long. What makes it look verbose is that you put each { or } on its own line. You can rewrite it like this:

#include <stdbool.h>

int compareHelper(const char *s, const char *regex, bool star)
{
    if (*s == '\0' && *regex == '\0')
        return true;

    if (*regex == '*')
        return compareHelper(s, regex + 1, 1); // star is seen hence will be set to true.

    if (!star) {
        if (*s != *regex)
            return false; // star was not seen and they differ in char
        else
            return compareHelper(s + 1, regex + 1, star);
    }

    // seen a star; look for the text after the star
    while (*s && *s != *regex)
        s++;

    if (*s == '\0')
        return 0;

    return compareHelper(s + 1, regex + 1, 0) || compareHelper(s + 1, regex, 1);
}

Some people will complain that "you must always use braces in if and while statements", but that's not necessary. If you properly indent your code or let your IDE format the code automatically, the indentation properly expresses the relation of the code pieces to each other. The typical example is:

if (condition)
    goto fail;
    goto fail;

Modern compilers not only translate the source code to machine code, they also check for various possible bugs in the code. Wrong indentation like in the above snippet is one of them.

And here's a complete implementation that also matches character ranges like [A-Z]. The code looks remarkably similar to yours, which is good. If you take that code and remove the part that handles the [A-Z] part, it will be very similar to your code. Actually, taking other people's code and editing it just trying to understand it is an efficient way of thinking about why each of these lines of code is actually necessary.

While reading that code, you may notice that your code might fail for str_match("a good game", "a *game"). You should verify that the search after the star looks at every possible position in the string, not only the first time the letter g appears.

\$\endgroup\$
3
  • \$\begingroup\$ The lack of braces { and } reduces the maintainability of the code. I agree they take up vertical space but I live with it. \$\endgroup\$
    – pacmaninbw
    Nov 19 '20 at 14:48
  • \$\begingroup\$ @Roland Illig, I very much appreciate your answer. \$\endgroup\$
    – Maor Rocky
    Nov 19 '20 at 19:07
  • \$\begingroup\$ @pacmaninbw That's exactly what I predicted: "Some people will complain". But I also explained in which environment (automatically formatted code) the braces are completely redundant and just take up screen space. Your argument "reduces the maintainability of the code" is quite abstract, it could mean anything. \$\endgroup\$ Nov 19 '20 at 21:58
2
\$\begingroup\$

Move your main() to the bottom, so you don't have to declare other functions, it's also less prone to errors.

'*' is not called a star, but it's called an asterisk.

Instead of using an additional function for hiding the argument int star, which acts as a memory, reduce to only one function and use a static int star as a function variable within that function.

I find your approach of a self calling recursive function interesting. You should make sure that it becomes never to an infinity loop, by counting each calls, probably within another static int function variable.

Please add some more comments, especially about the functionality of your function.

PS What happens when your search pattern argument begins with an asterisk, like "*a*b*c"?

PPS if your goal is to achieve the most performant solution, a self calling recursive function is not the fastest way to accomplish. Using a clever loop would be faster, you might even just use a goto to jump back to your function top line.

Example:

#include <stdio.h>
#include <string.h>
//uncomment the following line when using threads
//#include <threads.h>


int compareStrings(char *s, char *regex)
{
    //uncomment thread_local when using threads
    /*thread_local*/ static int star = 0;
    
    START:
    if (*s == '\0' && *regex == '\0')
    {
        return 1;
    } else if (*regex == '*')
    {
        //return compareHelper(s, regex + 1, 1); // star is seen hence will be set to true.
        regex++;
        star = 1;
        goto START;
    } else
    {
        if (!star)
        {
            if (*s != *regex)
            { // star was not seen and they differ in char
                return 0;
            } else
            {
                //return compareHelper(s + 1, regex + 1, star);
                s++;
                regex++;
                goto START;
            }

        } else
        {
            while (*s && *s != *regex)
            {
                s++;
            }
            if (*s == '\0') return 0;
            else
            {
                //I'm pretty sure your return statement can be reduced to a more elementar statement.
                //PS I'm not reducing it for you.
                //return compareHelper(s + 1, regex + 1, 0) | compareHelper(s + 1, regex, 1);
                star = 0;
                int a = compareStrings(s + 1, regex + 1);
                star = 1;
                int b = compareStrings(s + 1, regex);
                
                return a | b;
            }
        }
    }
}

int main()
{
    printf("%d\n", compareStrings("aaaacbbb", "a*b"));
    printf("%d\n", compareStrings("aaaabccccccccb", "a*b*c"));
    return 0;

}

PPPS please rethink about that statement: return compareHelper(s + 1, regex + 1, 0) | compareHelper(s + 1, regex, 1);, it probably can be simplified.

\$\endgroup\$
11
  • \$\begingroup\$ * is quite often called "star". At least round here, that is - it may vary by location. \$\endgroup\$ Nov 19 '20 at 12:53
  • \$\begingroup\$ There's no need for goto there - just use an ordinary loop (the non-goto cases all return, unless I'm missing something). \$\endgroup\$ Nov 19 '20 at 12:55
  • \$\begingroup\$ @TobySpeight I agree, but for an ordinary loop, OP would probably have to rewrite his entire function. A goto is a fast way to achieve higher performance with less work. PS I'm pretty sure OP's implementation of return compareHelper(s + 1, regex + 1, 0) | compareHelper(s + 1, regex, 1); is producing a lot of overhead, thus reducing performance. Some clever use of if...if else...else would surely help. \$\endgroup\$
    – paladin
    Nov 19 '20 at 12:58
  • 1
    \$\begingroup\$ Seriously, it's just a matter of removing the gotos and replacing the START: label with for (;;). :-) \$\endgroup\$ Nov 19 '20 at 13:08
  • 1
    \$\begingroup\$ The static variable is wrong here. There is absolutely no need to have a global variable here. The function that checks whether the pattern matches the string must be side-effect free. \$\endgroup\$ Nov 19 '20 at 13:30
-2
\$\begingroup\$
// The main function that checks if two given strings 
// match. The first string may contain wildcard characters 
bool match(char *first, char *second)
{
    // If we reach at the end of both strings, we are done
    if (*first == '\0' && *second == '\0')
        return true;

    // Make sure that the characters after '*' are present
    // in second string. This function assumes that the first
    // string will not contain two consecutive '*'
    if (*first == '*' && *(first + 1) != '\0' && *second == '\0')
        return false;

    // If the first string contains '?', or current characters
    // of both strings match
    if (*first == *second)
    {
        return match(first + 1, second + 1);
    }

    // If there is *, then there are two possibilities
    // a) We consider current character of second string
    // b) We ignore current character of second string.
    if (*first == '*')
        return match(first + 1, second) || match(first, second + 1);
    return false;
}
```
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Your "answer" does not qualify as a code review. You have merely written some code of your own, without even trying to discuss the original code. This makes your "answer" off-topic here. \$\endgroup\$ Nov 19 '20 at 14:07
  • \$\begingroup\$ You have merely written some code of your own He did it again! He already has written the OP! How confusing. And ridiculous. \$\endgroup\$
    – user232636
    Nov 20 '20 at 16:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.