-2
\$\begingroup\$

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);
}
\$\endgroup\$
  • 5
    \$\begingroup\$ Welcome to Code Review! Is this intended to be C? Or C++? C and C++ are different languages with very different programming techniques and idioms, so questions oriented to C and C++ are likely to generate very different reviews. Also, you seem to have violated the "do not use standard library" requirement by #include <stdio.h>. Is it meant to be something else? \$\endgroup\$ – L. F. Jan 27 '20 at 3:16
  • 1
    \$\begingroup\$ @L.F. <stdio.h> is for...well i/o. Code sold1er is trying to show an algorithm for find/replace in string...not re-implementing standard input/output. \$\endgroup\$ – Oliver Schönrock Jan 27 '20 at 7:53
  • \$\begingroup\$ I am having a closer look at your code. Your code current compiles as C. Without the STL (ie the algorithms in the std::) and in this sort of problem domain any C++ solution is going to be awfully close to the C solution. We could "introduce" some C++ eg constexpr for the enum, but it would be a bit arbitrary..? Is the aim to make the code "better and shorter" or "to use C++"? \$\endgroup\$ – Oliver Schönrock Jan 27 '20 at 8:11
  • 1
    \$\begingroup\$ @L.F. Also, i think your edit confuses things. I believe the original poster wrote "std", Jamal changed it to "STD", and you changed it to "standard". std has special meaning in C++, it's the namespace for the standard library, and that's what the OP meant I believe. (so <stdio.h> is not part of that, because it's a C header for input output and not part of namespace std::). I presume you know all this? \$\endgroup\$ – Oliver Schönrock Jan 27 '20 at 8:16
  • 2
    \$\begingroup\$ I see. Please edit your question to include this information. And then, please answer this question (as I mentioned in my first comment): C or C++? \$\endgroup\$ – L. F. Jan 27 '20 at 9:25
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks a lot for taking the time and listing all this valuable points. After re-reading I do agree my question and intentions are not clear. I will try to improve my questions as I go along. This is my first PR here though :). The main reason why I put on restriction not to use any library functions is for educational purposes. I wanted to write the algorithm myself to better understand the logic, fiddle around with pointers, and appreciate how much easier it would've been, if I used c or a c++ library functions. I want to understand and be able to solve this questions on an interview etc. \$\endgroup\$ – Code_So1dier Jan 27 '20 at 9:52
  • \$\begingroup\$ @Code_So1dier That's fair enough. It's good to do at least once. And yes it's painful and error prone. Don't do this in an interview! I would not want someone to code that in an interview. I would want them to use the STL or libc. But it's good for learning. If you try to pull out those sections as functions you should find that the algorithm becomes clearer. Since you are new: If you are happy with an answer, upvote it and accept it. \$\endgroup\$ – Oliver Schönrock Jan 27 '20 at 9:58
  • 1
    \$\begingroup\$ The comment I made regarding using a couple of lines in python is an example of solving a problem in multiple domains. Python here is at the top of programming language abstraction, where code is really easy to write and it utilises library calls, which is pre-compiled c. Then I solve the same question by using c++ with std library. Then goes c with standard library. Finally there is c without library calls, one solution with stack memory, another solution with heap memory. \$\endgroup\$ – Code_So1dier Jan 27 '20 at 10:03
  • \$\begingroup\$ @Code_So1dier Yes, exactly. You clearly understand how this all works. \$\endgroup\$ – Oliver Schönrock Jan 27 '20 at 10:04
  • \$\begingroup\$ I prefer nothing but you can do whatever. code-formatting just looks odd to me for C. \$\endgroup\$ – S.S. Anne Jan 28 '20 at 16:48
3
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ I don't think you can use a const int in an array size declaration. It has to be a #define (enum works too, but that's a style question). using a const int produces a VLA which is "optional" as per C11. \$\endgroup\$ – Oliver Schönrock Jan 27 '20 at 19:07
  • 2
    \$\begingroup\$ I disagree with you on "int const ARRAY_MAX2 = 50; // preferred method" - it would not even compile. Regarding "strstr(char *hay_stack, char *needle)" - yes it is a good way to wrap what I've written. I see your point regarding breaking up logic into smaller bits. \$\endgroup\$ – Code_So1dier Jan 27 '20 at 23:13
  • \$\begingroup\$ ARRAY_MAX3 usable in pre-processor, ARRAY_MAX2 not so much. Minor: I'd expect ARRAY_MAX2 in lower case. \$\endgroup\$ – chux - Reinstate Monica Jan 28 '20 at 4:05
  • \$\begingroup\$ In C++ we can use const int in constant expressions, but unfortunately C doesn't allow that. \$\endgroup\$ – L. F. Jan 28 '20 at 11:56
  • \$\begingroup\$ int const isn't a good idea. It will cause the compiler to check the variable at runtime and generate a VLA unless you compile with optimization. It will also cause a symbol to be generated. \$\endgroup\$ – S.S. Anne Jan 28 '20 at 12:30
1
\$\begingroup\$

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"?

\$\endgroup\$
  • \$\begingroup\$ Hmm. quite "Hungarian" that suggestion? \$\endgroup\$ – Oliver Schönrock Jan 27 '20 at 18:14
  • \$\begingroup\$ I agree with your point that "current" is too short of a name and could be improved here, and think that "pointer_into_original_string" is a bit too long :). May be current_character would be better. Regarding current = &(original[0]) - imho it is superfluous, but may be it highlights the intention more. \$\endgroup\$ – Code_So1dier Jan 27 '20 at 22:19
  • \$\begingroup\$ Because you don't want big names. If I tossed extremely descriptive variable names into my code I'd be well over 80 characters for each line and that makes it harder to read. \$\endgroup\$ – S.S. Anne Jan 28 '20 at 12:32

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