Fog Creek Software
Discussion Board




reverse a string - word by word

It says the solutiojn can be achieved by first reversing the string normally, and then just reversing each word. Can anybody share their C implentation for this? For example using recusion, using induction etc. Also can it handle adjacent (multiple) spaces between words?
Thx



 

Gerald
Wednesday, September 18, 2002

Why? So we can do your homework for you? :)

Michael H. Pryor
Wednesday, September 18, 2002


I would also be VERY interested in a C program capable of doing induction, and applying _that_ to manipulating pointers :-)

Yo
Friday, September 20, 2002

Once you have the whole string, you can do this:

1. Go to the start of the string.
2. Skip all leading whitespace.
3. when you encounter the first non-whitespace character, save the pointer to the beginning of the word.
4.  go until you find the end of the word.
5.  save the end of the string in a temp var
6.  pass the pointer to the begin of the word and the pointer to the end of the word and the pointer to the string to your reversestring() function.
7.  your string should now have the first word in the correct order.
8.  repeat from step 2 on, using the pointer saved in step 5 as your new beginning ptr.  And repeat until you get to '\0'

Tim
Tuesday, September 24, 2002

Not being a C programmer, I have little insight into pointers cetera. But look at the Python code I have pasted below. Great language to express algorithms like these...

# my own little reversing fn
def reverse1(str):
    front = 0
    back = len(str) - 1

    s = list(str)
    
    while front < back:
        s[front],s[back] = s[back],s[front]
        front, back = front + 1, back - 1
        
    return string.join(s,'')

# reversing string, word by word
def reverse3(str):
    str = reverse1(str)

    words = string.split(str)
    revwords = []
    for w in words:
        revwords.append(reverse1(w))
        
    return string.join(revwords)

# same thing, using Python fns
def reverse4(str):
    wordlist = string.split(str)
    wordlist.reverse()

    return string.join(wordlist)

Anirudh Moudgal
Monday, October 28, 2002

Reversing a string can also be expressed recursively: the reverse of a string is got be appending the reverse of the 1..n characters with the 0th character.

So it's an interesting question you can ask after asking the interviewee an algorithm for calculating the factorial of an integer.

Here is some Python code that does that:

def reverse(str):
    """Recursively reverse a string"""
    
    if len(str)==1:
        revstr=str
    else :
        revstr=reverse(str[1:])+str[0]
        
    return revstr

Anirudh Moudgal
Monday, October 28, 2002

*  Recent Topics

*  Fog Creek Home