Hello all,

Here I intend to reverse a line of text ending in a newline, but only the individual words will be reversed, not every character. For example, "This is just a test." would output ".test a just is This". The code as stands prints a space for every character in the word, as I cannot think of a way to recapture the previously read characters.

I think my professor is a sadist... we have to process the input one character at a time, recursively and cannot use any extraneous structures such as an array.

<disclaimer> This is just for bonus, and I intend to let him know that I received outside help on it. The actual assignment was to reverse a string of text, one character at a time, recursively.</disclaimer>

#include <stdio.h>

int reverseWords(int);

int main() {
    char ch;
    while ( (ch = getc(stdin)) != EOF ) {
        ungetc(ch,stdin);
        reverseWords(1);
        putc('\n', stdout);
    }
    return 0;
}

int reverseWords(int count) {
    char ch;
    ch = getc(stdin);
    if (ch == '\n') return;
    else if (ch == ' ') {
        for (count; count > 0; count--) {
            putc(ch, stdout);
        }
    }
    reverseWords(count+1);
}

Just for kicks, here is the (working) code to reverse a single line of text, preserving the newline at the end.

#include <stdio.h>

void reverseLine(void);

int main() {
    char ch;
    while ( (ch = getc(stdin)) != EOF ) {
        ungetc(ch,stdin);
        reverseLine();
        putc('\n', stdout);
    }
    return 0;
}

void reverseLine(void) {
    char ch;
    if ( (ch = getc(stdin)) == '\n') return;
    reverseLine();
    putc(ch, stdout);
}

Edited 6 Years Ago by holocron: n/a

have a look at this code

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

int main ()
{
  char str[] = "This is a sample string";
  char * pch;
  pch=strrchr(str,' ');
  while (pch)
  {
	  printf("%s",pch);
	  str[pch-str] = '\0';
	  pch=strrchr(str,' ');
	  if(!strrchr(str,' '))
	  {
		  printf(" %s",str);
		  break;
	  }
  }
  return 0;
}

have a look at this code

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

int main ()
{
  char str[] = "This is a sample string";
  char * pch;
  pch=strrchr(str,' ');
  while (pch)
  {
	  printf("%s",pch);
	  str[pch-str] = '\0';
	  pch=strrchr(str,' ');
	  if(!strrchr(str,' '))
	  {
		  printf(" %s",str);
		  break;
	  }
  }
  return 0;
}

You will notice that I need to be able to do this recursively, without using an array. Nice try though, thanks for the effort.

Your professor is sadistic? Well, I can be sadistic too.

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

int reverse( int code, char *start, int diff );

int main( void )
{
    char c;
    int diff;
    
    /* Figure out the size of runtime stack blocks. */
    diff = reverse( 1, NULL, 0 );

    /* Loop until EOF. */
    while (1)
    {
        c = getc( stdin );
        if ( c == EOF )
            break;
        else
            ungetc( c, stdin );
        
        reverse( 0, NULL, diff );
        putc( '\n', stdout );
    }
    
    return 0;
}

int reverse( int code, char *start, int diff )
{
    char VALUE;
    int res;
    
    /* Determine the span between invocations of the runtime stack. */
    if ( code == 1 ) return reverse( 2, &VALUE, 0 );
    if ( code == 2 ) return (&VALUE)-start;
    
    /* The actual code involved in reversing the string. We pass the front
       of the word to the end of the word to help unwind it. */
    VALUE = getc( stdin );
    if ( VALUE == EOF || VALUE == '\n' )
    {
        /* On traditional machines, the stack pointers go from higher space
           to lower space. I put this conditional for cross platform-ness. */
        while ( (diff < 0 && start > &VALUE) || (diff > 0 && start < &VALUE) )
        {
            putchar( *start );
            start += diff;
        }
    }
    else if ( start == NULL )
        reverse( code, &VALUE, diff );
    else if ( VALUE == ' ' )
        reverse( code, NULL, diff );
    else
        reverse( code, start, diff );
    
    /* Printing on the way down. */
    if ( VALUE == ' ' )
    {
        putchar( ' ' );
        while ( (diff < 0 && start > &VALUE) || (diff > 0 && start < &VALUE) )
        {
            putchar( *start );
            start += diff;
        }
    }
    
    return 0;
}

This code compiles. It works. It works on 3 seperate computers. But it's wrong on so many levels. It turns the runtime stack into a runtime array. It subverts the program requirements and will offend everyone on this forum that reads it.

That being said, I think its the only way to do it without a data structure. You simply don't have enough space to do what you want to do. Recursion is the answer, but I don't think this problem can be solved without having at least 2 fully functional stacks. I may be wrong, and I'd like to be wrong, but I do not believe there's a solution that fits your requirements.

Don't take my code seriously. I wrote it partially as a joke, and partially to make myself feel better after spending so much time on this. This has been on my mind literally since you posted it.

Wow, thank you so much. I am inclined to think as you do, while I do not have the skill to pull this level of code out of my arse, I am glad that you can.

Most likely he did not expect us to actually do it one char at a time, even though that was the specification.

After the due date, I will show this code to the class and see if he was actually able to do it without munging the runtime stack...

Thanks again, that is awesome!

If you can use loops,
- recurse to the end of the string as before
- don't output during the return spin until you reach a space
- if space, loop outputting the characters following the space up to the next space or '\n'

If you can't, set up one more recursive function that outputs a single character and increments until space or \n.

IOW, to reverse a string you output during the return cycle
To print the string straight you output during the call cycle, Nothing happens during the returns.

If you can use loops,
- recurse to the end of the string as before
- don't output during the return spin until you reach a space
- if space, loop outputting the characters following the space up to the next space or '\n'

If you can't, set up one more recursive function that outputs a single character and increments until space or \n.

IOW, to reverse a string you output during the return cycle
To print the string straight you output during the call cycle, Nothing happens during the returns.

But how do we do any of those with standard input? The only way to print the last word in the string is to getc every character out of the stream. Once we've done that, we are responsible for maintaining all of them - the stream is empty.

The algorithm you provided works so long as we can move through the string multiple times. As far as I can tell from the requirements, that is not the case.

This is from the specifications:

BONUS: For a maximum 50% bonus, not only reverse the line but reverse the words within the line, recursively. By definition, a word is a sequence of alpha-numeric characters.
Call this program reverseWords.
For example, the line containing "Howdy doody time." should come out looking like ".time doody Howdy". As with reverse, we should reach identity such that we could test with ./reverseWords < someFile | ./reverseWords > someOtherFile followed by the diff someFile someOtherFile.
This can be accomplished one character at a time with no extraneous data structures. However, if you cannot accomplish that, then use the simplest data structure you can.

I take this to mean that we can do looping within the recursion or make another recursion occur during the unwind. I tried a few different implementations of your suggestion WaltP, but I could get none to work properly.

I thought about using a file stream to store the reversed line and then making a call to a 2nd recursive function that would parse that stream and reverse the individual words, but this turned out to be beyond my capabilities.

I don't necessarily consider an array to be a data structure, so I read the line into an array. Maybe your instructor does. I suppose you could do it by reading a character at a time and just deal with the character.

you can use the "strrev" function to do so.
example strrev(stringname)

Comments
How the H*** does strrev() use recursion?

you can use the "strrev" function to do so.
example strrev(stringname)

If you don't understand the question, don't offer suggestions please.

This article has been dead for over six months. Start a new discussion instead.