Find and replace a string in C/C++ without using standard library [closed]

Question

I'm solving a problem with find and replace a substring in a string. I've solved it using Python with a couple of lines, in C++ using std library and now solved it with C by using allocation on the stack. I want to get genuine feedback on the code I wrote and perhaps make it simpler.

The constraints:

• do not use standard library, write logic by hand. (I've included stdio.h primarily for debugging. Final version of the algorithm could be a function like: void find_and_replace(char* source, char* find, char* replace); )

Requirements:

• Replace should replace all matches
• Match and replace same length string
• Replace longer match with shorter replacement
• Replace shorter match with longer replacement

#include <stdio.h>

int main()
{
    enum SIZE
    {
        ARRAY_MAX = 50
    };

    char original[ARRAY_MAX] = "one two three two\0";
    char find[ARRAY_MAX] = "two\0";
    char replace[ARRAY_MAX] = "22222\0";

    printf("original: %s\n", original);
    printf("find: %s\n", find);
    printf("replace: %s\n", replace);

    char* current = original;
    while (*current != '\0')
    {
        if (*current == find[0])
        {
            char* match_iter = current;
            char* find_iter = find;
            int match = 0;
            while(*match_iter!='\0' && *find_iter!='\0')
            {
                if (*match_iter == *find_iter)
                {
                    match = 1;
                }
                else
                {
                    match = 0;
                    break;
                }
                match_iter++;
                find_iter++;
            }

            if (match)
            {
                printf("the whole word matched\n");
                find_iter = find;
                char* replace_iter = replace;
                while(*find_iter != '\0' &&
                      *current != '\0' &&
                      *replace_iter != '\0')
                {
                    *current = *replace_iter;
                    ++find_iter;
                    ++replace_iter;
                    ++current;
                }
                if (*find_iter != '\0' &&
                    *replace_iter == '\0')
                {
                    printf("match is longer than replace\n");

                    char* move_left = current;
                    while(*find_iter != '\0' &&
                          *move_left != '\0')
                    {
                        ++find_iter;
                        ++move_left;
                    }

                    char* temp_current = current;
                    while(*move_left != '\0' &&
                          *temp_current != '\0')
                    {
                        *temp_current = *move_left;
                        ++temp_current;
                        ++move_left;
                    }

                    *temp_current = '\0';
                }
                else if (*find_iter == '\0' &&
                         *replace_iter != '\0')
                {
                    printf("replace is longer than match\n");
                    char* move_right = current;
                    char temp[ARRAY_MAX];
                    char* temp_iter = temp;
                    while(*replace_iter != '\0')
                    {
                        *temp_iter = *current;
                        *current = *replace_iter;
                        ++current;
                        ++temp_iter;
                        ++replace_iter;
                    }

                    char* current_to_end = current;
                    while(*current_to_end != '\0')
                    {
                        *temp_iter = *current_to_end;
                        ++temp_iter;
                        ++current_to_end;
                    }

                    *temp_iter = '\0';

                    temp_iter = temp;
                    char* temp_current = current;
                    while(*temp_iter != '\0')
                    {
                        *temp_current = *temp_iter;
                        ++temp_current;
                        ++temp_iter;
                    }
                    *temp_current = '\0';
                }
                else if (*find_iter == '\0' &&
                         *replace_iter == '\0')
                {
                    printf("replace and match are same length\n");
                }

            }
            else
            {
                printf("only a fraction matched\n");
            }
        }

        ++current;
    }

    printf("The sentence after replacement: %s\n", original);
}

Answer 1

Aim

It's not 100% clear in your question, but what I am assuming is that you would like some feedback on:

• How to utilize C++ for this problem domain without using the STL (ie namespace std::)
• How to improve / re-structure the code to make it "better and shorter".

Just a general point. Obviously both C and C++ have standard functions and algorithms for doing this task. You have said that don't want to use these. You have not said "why". Perhaps you are on an embedded system, so C++ STL is not available? But then C stdlib.h should still be available and it has building blocks which you could be using (e.g. strstr strncpy) thereby avoiding quite so much manual pointer fiddling. So is your constraint of hand-coding this purely for educational purposes, or is there a possibility of at least using stdlib (which is also available under C++, of course)?

Evaluating existing code

• Compiles => good
• Works => good
• doesn't appear to leak memory or access out of bounds (I only ran valgrind, more checks are needed) => good

• One warning generated:

  fr.cpp:60:17: warning: unused variable 'move_right' [-Wunused-variable]
      char* move_right = current;
  

  if I enable -Wall -Wextra on clang. You should turn warnings on and address them.

• Structure: One big while loop => could be better.
• Clarity: Related to structure. Without diving deep and putting my "pointer-foo" hat on, it's not trivial to understand what the code is doing. I get the general idea, but it's not very clear.

Feedback

Follows straight from the evaluation:

• Decide what you can and cannot use. Is stdlib (as opposed to C++ std::) allowed? If not, why not? If so, you should use it. I could show how, but it's been done already: https://www.geeksforgeeks.org/c-program-replace-word-text-another-given-word/. That example uses the heap, but could be easily adapted to use the stack. Although the problem with any stack implementation (including yours) is that the max_length needs to be fixed at compile time. If I change your replace string to something > 25 characters long (replaced twice) the program segfaults due to clobbering its own stack.
• Decide if this is just an educational exercise and you do not want to use stdlib string primitives. The main answer to improving your code is using functions. Using functions will make each piece more digestible. Using good names for your functions will make the code self-documenting. A casual reader might get close to being able to read it like an English sentence.

If you look at the link above, it shows you how the primitives can be used to make the code more readable, maintainable, reusable, and shorter. If you were to start with your own code and pull out some sections of the while loop as functions, you may find that the functions you pull out are very similar to the stdlib primitives.

This could be a neat piece of experience. If you are unsure how to split your while loop, you could let the example above using the C library primitives guide you. Or you could do it blind and find out if you end up with similar functions/abstractions as the C library writers did.

In the end main() should be a few lines, and each function should be no longer than say 10-15 lines at most.

Assuming educational purpose, it would be better for you to try to pull out those sections rather than having someone do it for you. You learn more that way.

Some C++ points:

• If you don't use any library at all, then, for this specific problem domain, the difference between C and C++ is going to be minimal. However, in general, one of big gains of using C++ over C for day-to-day usage is the convenience of handling strings using std::string. No more malloc strncpy strdup strstr etc.
• in C++ the include should be #include <cstdio>
• C++ usually shouldn't use printf, but std::cout (assuming you don't mind about I/O using a base lib, as you already are).
• You should use a constexpr variable for ARRAY_MAX. enum is "one of set", which is not the case. (In C you should use a #define for this).

Python comparison

I feel the "few lines of python" comparison is not very relevant, because:

• a manually coded str_replace in python is likely to be unacceptably slow as a general function
• the operators you would have likely used in python (eg str1 = str2) are just calling some C or C++ function which are using strncpy/std::string operator=() or similar.
• So to use those operators in python, but refuse to use the C-functions is not a reasonable comparison IMO.

Hope that gives you something to get on with.

Answer 2

As mentioned in another answer, the best improvements to the code would be a function that is the equivelent of the C library function strstr(char *hay_stack, char *needle) and a function that replaces the string. This would simplify the main() function. One of the basic ways of writing a program is to keep breaking the problem down until the result is small functions that are easy to implement. The function strstr() can be written in less than 15 minutes, I know this because I used to use implement strstr() as an interview question.

This would also reduce the number of variables required in main() and you wouldn't need to worry about partial matches.

Defining Symbolic Constants

In the code ARRAY_MAX is defined using an enum, and it is not really clear why. In C++ this could be defined using

int constexpr ARRAY_MAX = 50;

and in the C programming language

int const ARRAY_MAX2 = 50;  // preferred method

or

#define ARRAY_MAX3  50  // Almost obsolete

Answer 3

Comment about your naming conventions. Statements such as current = original show that you conflate the array and the pointer view of things. Clearly original refers to a string, whereas current seems to be "the current location in the string". (I would be almost tempted to write current = &(original[0]) just to show what's happening.)

However, the name current gives no indication of what type it is: a current what?. Also, the expression *current indicates that current is not "current character" but "pointer to current character".

How about you use more descriptive names, such as "pointer_into_original_string"?