Friday, May 24, 2013

Reverse String and Sentence


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

#define SPACE 32

//===================================

void SwapInPlace(char * a, char * b){
    if ( *a != *b ){
        *a = *a ^ *b;
        *b = *a ^ *b;
        *a = *a ^ *b;
    }
}

void ReverseInPlace(char* src){
    size_t len, i, m, n;

    len = strlen(src);
    for ( i=0 ; i < len ; ++i ){
        if ( *(src+i) == SPACE )        {
            for ( m=0 ; m <= i-1 ; ++m ){
                for ( n=0 ; n < len-1 ; ++n ){
                    SwapInPlace(src+n, src+(len+n+1)%len);
                }
            }
            len -= i;
            for ( n=0 ; n < len-1 ; ++n )            {
                SwapInPlace(src+n, src+(len+n+1)%len);
            }
            len--;
            i = -1;
        }
    }
}

void ReverseInPlace2(char* src)
{
    size_t i, j, start;
    size_t len = strlen(src);
    for ( i=0 ; i < len/2 ; ++i )
    {
        SwapInPlace(src+i, src+len-1-i);
    }
    start = 0;
    for ( i=0 ; i < len ; ++i )
    {
        if ( *(src+i) == SPACE || i == len-1 )
        {
            if ( i== len-1 ) i++;
            for ( j=0 ; j < (i-start)/2 ; ++j )
            {
                SwapInPlace(src+start+j, src+i-1-j);
            }
            start = i+1;
        }
    }
}
//===================================

void Reverse(char *pBegin, char *pEnd){
    char temp ;

    if(pBegin == NULL || pEnd == NULL) return;

    while(pBegin < pEnd){
        temp = *pBegin;
        *pBegin = *pEnd;
        *pEnd = temp;

        pBegin ++, pEnd --;
    }
}

char* ReverseSentence(char *pData){
    char *pBegin, *pEnd;

    if(pData == NULL) return NULL;

    pBegin = pData;
    pEnd = pData;

    while(*pEnd != '\0')
        pEnd ++;
    pEnd--;

    Reverse(pBegin, pEnd);    // Reverse the whole sentence


    // Reverse every word in the sentence

    pBegin = pEnd = pData;
    while(*pBegin != '\0'){
        if(*pBegin == ' '){
             pBegin ++;
             pEnd ++;
             continue;
        }
        // A word is between with pBegin and pEnd, reverse it

        else if(*pEnd == ' ' || *pEnd == '\0')        {
             Reverse(pBegin, --pEnd);
             pBegin = ++pEnd;
        }
        else{
             pEnd ++;
        }
    }

    return pData;
}
//===================================

void reverse(char *str){
    char tmp;
    int len, i, j;

    len = strlen(str);
    for(i = 0, j = len-1; i < len/2; i++, j--) {
     tmp = str[i];
     str[i] = str[j];
     str[j] = tmp;
    }
}

void composeStrFromArray(const char* str, const unsigned from, const unsigned to, char* tmp){
    const char *i = str+from;
    unsigned j = 0;

    for(; i <= str+to; i++, j++ ){
        tmp[j] = *i;
    }
    tmp[j] = '\0';
}

void printi(const char* str, const unsigned from, const unsigned to){
    unsigned i;
    for(i = from; i <= to; i++ ){
        printf("%c", str[i]);
    }
    printf("\n");
}

void reverseSentence(const char* str, char* tmp){
    unsigned i, sI;
    unsigned notPrinted = 1;    //boolean, not print the word

    char ttt[100] = {'\0'};    

    for(i = 0, sI = 0; i <= strlen(str); i++){
        if( str[i] == ' ' || str[i] == '\t' || str[i] == '\0' ){
            if(! notPrinted) continue;

            composeStrFromArray(str, sI, i-1, ttt);
            reverse(ttt);
            strcat(tmp, ttt);
            
            if(str[i] != '\0')
                strcat(tmp, " ");

            printf("%i %i -> ", sI, i-1);
            printi(str, sI, i-1);
            notPrinted = 0;
        }            
        else{
            if(! notPrinted) {
                sI = i;
                notPrinted = 1;
            }
        }
    }
}

void main(){
    char str[100] = {'\0'};
    char tmp[100] = {'\0'};
    char ttt[100] = {'\0'};
    char a, b;
    int n[] = {1,2,3,4,5};

    gets(str);
    strcpy(tmp, str);
    strcpy(ttt, str);
    printf("original string: %s\n", str);

    //my test

    reverse(str);
    printf("reversed string: %s\n\n", str);

    tmp[0] = '\0';
    reverseSentence(str, tmp);
    printf("reversed words: %s ->length: %i\n\n", tmp, strlen(tmp));

    //sample code 1

    ReverseSentence(tmp);
    printf("Reversed words: %s\n\n", tmp);

    //sample code 2

    printf("SRC: %s\r\n", ttt);
    ReverseInPlace(ttt);
    printf("DES: %s\r\n", ttt);
    ReverseInPlace2(ttt);
    printf("SRC: %s\n\n", ttt);

    // << multiple 2 and >> divide 2

    printf("shift left << %d\n", 9 << 1 );
    printf("shift right << %d\n", 9 >> 1 );

    a = 'a';
    b = 'b';
    SwapInPlace(&a, &b);
    printf("use XOR to swap a b : %c %c\n\n", a, b);
}

No comments: