The C Programming Language, 2nd Edition, by Kernighan and Ritchie
Exercise 5.06 on page 107
Rewrite appropriate programs from earlier chapters and exercises with pointers instead of array indexing. Good possibilities include getline (Chapters 1 and 4), atoi , itoa , and their variants (Chapters 2, 3, and 4), reverse (Chapter 3), and strindex and getop (Chapter 4).
Solution by Gregory Pietsch
/* Gregory Pietsch ex. 5-6 dated 2001-01-29 */ #include <ctype.h> #include <stdio.h> #include <stdlib.h> /* getline: get line into s, return length */ int getline(char *s, int lim) { char *p; int c; p = s; while (--lim > 0 && (c = getchar()) != EOF && c != '\n') *p++ = c; if (c == '\n') *p++ = c; *p = '\0'; return (int)(p - s); } /* atoi: convert s to an integer * * Here's the easy way: * int atoi(char *s){return (int)strtoul(s, NULL, 10);} * But I'll behave... */ int atoi(char *s) { int n, sign; while (isspace(*s)) s++; sign = (*s == '+' || *s == '-') ? ((*s++ == '+') ? 1 : -1) : 1; for (n = 0; isdigit(*s); s++) n = (n * 10) + (*s - '0'); /* note to language lawyers -- * the digits are in consecutive * order in the character set * C90 5.2.1 */ return sign * n; } /* Shamelessly copied from my 4-12 answer itoa() is non-standard, but defined on p.64 as having this prototype: void itoa(int n, char s[]) Instead of this, I thought I'd use a different prototype (one I got from the library manual of one of my compilers) since it includes all of the above: char *itoa(int value, char *digits, int base); Description: The itoa() function converts an integer value into an ASCII string of digits. The base argument specifies the number base for the conversion. The base must be a value in the range [2..36], where 2 is binary, 8 is octal, 10 is decimal, and 16 is hexadecimal. The buffer pointed to by digits must be large enough to hold the ASCII string of digits plus a terminating null character. The maximum amount of buffer space used is the precision of an int in bits + 2 (one for the sign and one for the terminating null). Returns: digits, or NULL if error. */ char *utoa(unsigned value, char *digits, int base) { char *s, *p; s = "0123456789abcdefghijklmnopqrstuvwxyz"; /* don't care if s is in * read-only memory */ if (base == 0) base = 10; if (digits == NULL || base < 2 || base > 36) return NULL; if (value < (unsigned) base) { digits[0] = s[value]; digits[1] = '\0'; } else { for (p = utoa(value / ((unsigned)base), digits, base); *p; p++); utoa( value % ((unsigned)base), p, base); } return digits; } char *itoa(int value, char *digits, int base) { char *d; unsigned u; /* assume unsigned is big enough to hold all the * unsigned values -x could possibly be -- don't * know how well this assumption holds on the * DeathStation 9000, so beware of nasal demons */ d = digits; if (base == 0) base = 10; if (digits == NULL || base < 2 || base > 36) return NULL; if (value < 0) { *d++ = '-'; u = -((unsigned)value); } else u = value; utoa(u, d, base); return digits; } /* reverse, shamelessly copied from my 4-13 answer */ static void swap(char *a, char *b, size_t n) { while (n--) { *a ^= *b; *b ^= *a; *a ^= *b; a++; b++; } } void my_memrev(char *s, size_t n) { switch (n) { case 0: case 1: break; case 2: case 3: swap(s, s + n - 1, 1); break; default: my_memrev(s, n / 2); my_memrev(s + ((n + 1) / 2), n / 2); swap(s, s + ((n + 1) / 2), n / 2); break; } } void reverse(char *s) { char *p; for (p = s; *p; p++) ; my_memrev(s, (size_t)(p - s)); } /* strindex: return index of t in s, -1 if not found */ /* needed strchr(), so here it is: */ static char *strchr(char *s, int c) { char ch = c; for ( ; *s != ch; ++s) if (*s == '\0') return NULL; return s; } int strindex(char *s, char *t) { char *u, *v, *w; if (*t == '\0') return 0; for (u = s; (u = strchr(u, *t)) != NULL; ++u) { for (v = u, w = t; ; ) if (*++w == '\0') return (int)(u - s); else if (*++v != *w) break; } return -1; } /* getop */ #define NUMBER '0' /* from Chapter 4 */ int getop(char *s) { int c; while ((*s = c = getch()) == ' ' || c == '\t') ; *(s + 1) = '\0'; if (!isdigit(c) && c != '.') return c; /* not a number */ if (isdigit(c)) /* collect integer part */ while (isdigit(*++s = c = getch())) ; if (c == '.') /* collect fraction part */ while (isdigit(*++s = c = getch())) ; *++s = '\0'; if (c != EOF) ungetch(c); return NUMBER; } /* Is there any more? */
Solution by Jesus Alvarez (Category 0)
#include <stdio.h> #include <string.h> #include <ctype.h> #define STR_MAX 10000 #define BUFSIZE 100 #define NUMBER '0' char *my_getline (char *, int); char *itoa (int, char *); int atoi (char *); char *strrev (char *); int strindex (char *, char *); int getop (char *); int getch (void); void ungetch (int); int main(int argc, char *argv[]) { int num; char ss1[STR_MAX]; char ss2[STR_MAX]; char atoi_buf[STR_MAX]; char itoa_buf[STR_MAX]; int type; char s[BUFSIZE]; printf (">>> Please enter a number: "); my_getline(atoi_buf, STR_MAX); num = atoi(atoi_buf); printf ("\natoi: str: %s, int: %d\n", atoi_buf, num); printf ("itoa: int: %d, str: %s\n\n", num, itoa(num, itoa_buf)); printf (">>> Enter string 1: "); my_getline(ss1,STR_MAX); printf (">>> Enter string 2: "); my_getline(ss2,STR_MAX); printf ("\nThe reverse of string 1: %s\n", strrev(ss1)); printf ("The reverse of string 2: %s\n", strrev(ss2)); num = strindex(ss1, ss2); if (num == -1) { printf("\nThe substring (string 2) was not found in the "); printf("base string (string 1).\n\n"); } else { printf("\nThe substring was found in the base string, "); printf("starting at position %d.\n\n", num); } printf (">>> Please enter a simple equation (parsing example using getop()).\n"); printf (">>> Example: 100+1039.238-acd\n"); while ((type = getop(s)) != EOF) { switch (type) { case NUMBER: printf ("Found a number: %s\n", s); break; case '+': printf ("Found \'+\'\n"); break; case '\n': printf ("Found Line Break.\n"); break; default: printf ("Found something else: %s\n", s); break; } } return 0; } char *my_getline(char *str, int str_max) { char c; /* * A local variable to perform arithmetic on so that 'str' points to * the correct location when it is passed back to the caller. */ char *s1 = str; while ((c = getchar()) != EOF && c != '\n' && str_max-- > 0 ) { *s1++ = c; } if (*s1 == '\n') { *s1++ = c; } *s1 = '\0'; return str; } char *itoa(int num, char *str) { char *ls = str; do { *ls++ = num % 10 + '0'; } while ((num /= 10) > 0); strrev(str); return str; } int atoi(char *str) { int n, sign; while (isspace(*str)) { str++; } sign = (*str == '-') ? -1 : 1; if (*str == '+' || *str == '-') { str++; } for (n = 0; isdigit(*str); str++) { n = 10 * n + (*str - '0'); } return n * sign; } char *strrev(char *str) { int i; char c; char *lp1 = str; /* The start of str. */ char *lp2 = str; /* The end of str, for incrementing. */ char *lp3 = str; /* The end of str, for reference. */ i = strlen(str)-1; lp2 += i; lp3 += i; do { c = *lp1; *lp1++ = *lp2; *lp2-- = c; } while ((i -= 2) > 0); *++lp3 = '\0'; return str; } int strindex(char *s, char *t) { int i, j; char *sb = s; char *ss = s; char *tb = t; for (i = 0; *sb != '\0'; i++, sb++) { tb = t; /* Reset the pointer to the beginning of the string. */ ss = sb; /* Reset the substring pointer to the base string * pointer. */ for (j = 0; *tb != '\0' && *ss == *tb; ss++, tb++, j++) { if (*(tb+1) == '\0' && j > 0) { return i; } } } return -1; } int getop (char *str) { int c; while ((*str++ = c = getch()) == ' ' || c == '\t'); *str = '\0'; if (!isdigit(c) && c != '.') { return c; } if (isdigit(c)) { while (isdigit(*str++ = c = getch())); } if (c == '.') { /* Collect fraction. */ while (isdigit(*str++ = c = getch())); } *--str = '\0'; /* Compensate for the extra character. */ if (c != EOF) { ungetch(c); /* Return extra charater to the stack. */ } return NUMBER; } char buf[BUFSIZE]; /* The Stack */ int bufp = 0; /* Top Position on the stack */ int getch (void) { return (bufp > 0) ? buf[--bufp] : getchar(); } void ungetch (int c) { if (bufp >= BUFSIZE) { printf("ungetch: too many characters.\n"); } else { buf[bufp++] = c; } }
Solution by menonsahab
/**************************** atoi() ********************************/ #include <stdio.h> #include <ctype.h> #define SIZE 100 int main() { char str[SIZE]; scanf("%s", str); printf("string = %s, number = %d\n", str, atoi(str)); return 0; } int atoi(char *s) { int sign, n = 0; while(isspace(*s)) s++; sign = (*s == '-') ? -1 : 1; if(*s == '+' || *s == '-') s++; while(isdigit(*s)) { n = 10 * n + (*s-'0'); s++; } return sign*n; } /********************************************************************/ /*************************** itoa() *********************************/ #include <stdio.h> #define SIZE 100 char *itoa(int n, char *s); void reverse(char *s); int main() { int num; char str[SIZE]; scanf("%d", &num); printf("num = %d, string = %s\n", num, itoa(num, str)); return 0; } char *itoa(int n, char *s) { int sign; char *p = s; sign = (n < 0) ? -1 : 1; (sign < 0) ? n = -n : 0; // Won't work for n = INT_MIN, store -n in an unsigned variable if required while(n > 0) { *p++ = n%10 + '0'; n = n / 10; } (sign == -1) ? (*p++ = '-') : 0; *p = '\0'; reverse(s); return s; } void reverse(char *s) { char *p; int temp; p = s; while(*p) p++; p--; while(s<=p) { temp = *s; *s = *p; *p = temp; s++; p--; } } /********************************************************************/ /**************************** reverse() *****************************/ #include <stdio.h> #define SIZE 100 void reverse(char *s); int main() { char str[SIZE]; scanf("%s", str); printf("string = %s\n", str); reverse(str); printf("reversed string = %s\n", str); return 0; } void reverse(char *s) { char *p; int temp; p = s; while(*p) p++; p--; while(s<=p) { temp = *s; *s = *p; *p = temp; s++; p--; } } /********************************************************************/ /****************************** strindex() **************************/ #include <stdio.h> #define SIZE 100 int main() { char s[SIZE], t[SIZE]; scanf("%s", s); scanf("%s", t); printf("strindex(%s, %s) = %d\n", s, t, strindex(s, t)); return 0; } int strindex(char *s, char *t) { int tlen, count; char *p, *q, *r; q = t; while(*q++); q--; tlen = q-t; for(p = s; *p ; p++) { count = 0; r = p; for(q = t; *q ; q++, r++) { if(*r == *q) count++; else break; } if(count == tlen) return (int)(p-s); } return -1; } /********************************************************************/ /**************************** getop() *******************************/ #include <stdio.h> #include <ctype.h> #define SIZE 100 #define NUMBER '0' #define BUFSIZE 100 char buf[BUFSIZE]; int bufp = 0; int getch(void) { return (bufp>0) ? buf[--bufp] : getchar(); } void ungetch(int c) { if(bufp >= BUFSIZE) printf("ungetch: too many characters\n"); else buf[bufp++] = c; } int main() { char str[SIZE]; int type; while((type = getop(str)) != EOF) printf("type = %d, str = %s\n", type, str); return 0; } int getop(char *s) { int c; while(isspace(*s = c = getch())); *(s+1) = '\0'; if(!isdigit(c) && c != '.') return c; if(isdigit(c)) while(isdigit(*++s = c = getch())); if(c == '.') while(isdigit(*++s = c = getch())); *++s = '\0'; if(c != EOF) ungetch(c); return NUMBER; } /********************************************************************/
Solution by Luke Panayi
Here are my solution, excluding getop:
/* * Rewrite appropiate programs from earlier chapters and exercises * with pointers instead of array indexing. Good possibilites include getline * (Chapters 1 and 4), atoi, itoa, and their varients (Chapters 2, 3, and 4), * reverse (Chapter 3), and strindex and getop (Chapter 4). */ #include <stdio.h> #include <ctype.h> #include <math.h> #define BUFFER 1000 // getline: read a line into s, return length int getline2(char *s, int lim) { int i, c; for (i=0; i<lim-1 && (c=getchar()) != '\n' && c != EOF; ++i) *s++ = c; *s = '\0'; return i; } // reverse: reverse the character string s char *reverse(char *s) { int i, strlen; char tmp, *sStart = s; while (*++s); s--; //don't reverse the null character! strlen = s - sStart; strlen = strlen % 2 == 0 ? strlen : strlen+1; //deal with odd length strings for (i=0; i < strlen/2; ++i) { tmp = *(sStart+i); *(sStart+i) = *(s-i); *(s-i) = tmp; } return sStart; } // atof: convert s to float double atof(char *s) { double n; for (; isspace(*s) || *s == '\t'; ++s); for (n=0; isdigit(*s); ++s) n = n * 10 + (*s - '0'); if (*s++ == '.') { int i, d; for (i=0, d=0; isdigit(*s); ++i, ++s) d = d * 10 + (*s - '0'); n+=(d/pow(10,i)); } return n; } // itoa: convert n to characters in s char *itoa(int n, char *s) { int sign; char *sStart = s; if ((sign = n) < 0) n = -n; do { *++s = n % 10 + '0'; } while (n/=10); if (sign < 0) *++s = '-'; *++s = '\0'; return reverse(sStart); } // strrindex: return the position of the rightmost occurrence of t in s, or -1 if there is none int strrindex(char *s, char *t) { char *sStart = s, *tStart = t; while (*++s) { if (*s == *t) { char *rS = s; while (*++s == *++t) { if (!*t) return rS - sStart; } t = tStart; } } return -1; } int main() { char s[BUFFER]; printf("%d\n", strrindex("hello world!", "world!")); return 0; }
Solution by anonymous
I re-wrote both getline and atoi functions, all four itoa functions, and the atof, reverse, strindex, and getop functions. During the conversion, I did my best to keep the original structure and logic of the code. I prioritized using pure pointers and removing the ints used for array indexing, but I found it difficult to do this for the recursive itoa function from chapter 4. Consequently, I just did the easy conversion process for that one (replacing s[i] with *(s + i).
#include <stdio.h> #include <ctype.h> #include <math.h> #include <string.h> #include <limits.h> /* Exercise 5-6. Rewrite appropriate programs from earlier chapters and exercises with pointers instead of array indexing. Good possibilities include getline (Chapters 1 and 4), atoi, itoa, and their variants (Chapters 2, 3, and 4), reverse (Chapter 3), and strindex and getop (Chapter 4). */ #define NUMBER '0' // for getop: signal that a number was found #define BUFSIZE 100 // for ungetch and buf variable char buf[BUFSIZE]; // for ungetch, getch: holds char buffer int bufp = 0; // for ungetch, getch: next free position in buf int getline(char *line, int maxlinesize); int getline2(char *s, int lim); int atoi1(char *s); int atoi2(char *s); double atof1(char *s); void itoa1(int n, char *s); void itoa2(int n, char *s); void itoa3(int n, char *s, int width); void itoa4(int n, char *s); void reverse(char *s); int strindex(char *s, char *t); int getop(char *s); int getch(void); void ungetch(int c); int main() { char str[1000]; printf("%d\n", getline(str, 1000)); printf("%s", str); printf("%d\n", getline2(str, 1000)); printf("%s", str); printf("%d\n", atoi1("1234567890 ")); printf("%d\n", atoi2(" -1235557890 ")); printf("%f\n", atof1(" -0123.456789 ")); itoa1(-1234567770, str); printf("%s\n", str); itoa2(INT_MIN, str); printf("%s\n", str); itoa3(7, str, 3); printf("%s\n", str); itoa4(INT_MAX, str); printf("%s\n", str); char str2[] = "detartrated!"; reverse(str2); printf("%s\n", str2); reverse(str2); // put in back to normal for strindex printf("%d\n", strindex(str2, "tart")); printf("%d\n", strindex(str2, "Detartrated!")); printf("%c\n", getop(str2)); printf("%s\n", str2); return 0; } // chapter 1 getline, page 29: get line into line, return length int getline(char *line, int maxlinesize) { int c; char *original = line; while (original - line < maxlinesize - 1 && (c = getchar()) != EOF && c != '\n') *line++ = c; if (c == '\n') *line++ = c; *line = '\0'; return line - original; } // chapter 4 getline, page 69: get line into s, return length int getline2(char *s, int lim) { int c; char *original = s; while (--lim > 0 && (c=getchar()) != EOF && c != '\n') *s++ = c; if (c == '\n') *s++ = c; *s = '\0'; return s - original; // returns length } // chapter 2 atoi, page 43: naive atoi: converts string to integer int atoi1(char *s) { int n = 0; // set to zero in case there are no numbers in string for ( ; *s >= '0' && *s <= '9'; s++) n = 10 * n + (*s - '0'); return n; } // chapter 3 atoi, page 61: handles leading whitespace and negative values int atoi2(char *s) { int sign, n = 0; // set n to zero in case there are no numbers in string while (isspace(*s)) // skip white space s++; sign = (*s == '-') ? -1 : 1; if (*s == '-' || *s == '+') // skip any sign s++; while (isdigit(*s)) n = 10 * n + (*s++ - '0'); // 10 * n adds a zero to right side, then add new number found to right side return sign * n; } // chapter 4 atof, page 71: convert string s to double double atof1(char *s) { double val = 0.0, power = 1.0; int sign; while (isspace(*s)) // skip white space s++; sign = (*s == '-') ? -1 : 1; if (*s == '+' || *s == '-') // skip symbol s++; while (isdigit(*s)) val = 10.0 * val + (*s++ - '0'); if (*s == '.') // skip symbol s++; while (isdigit(*s)) { val = 10.0 * val + (*s++ - '0'); power *= 10.0; } return sign * val / power; } // chapter 3, page 64: convert n to characters in s void itoa1(int n, char *s) { int sign; char *original = s; // keep original pointer location if ((sign = n) < 0) // record sign n = -n; // make n positive do // loop gets digits in reverse order { *s++ = n % 10 + '0'; // get next digit } while ((n /= 10) > 0); // remove digit captured via integer division if (sign < 0) *s++ = '-'; *s = '\0'; reverse(original); // once reversed, everything is in the correct order (send original pointer to reverse function) } // chapter 3 itoa, exercise 3-4: handles the largest negative number void itoa2(int n, char *s) { int sign; char *original = s; // keep original pointer location sign = n; do { *s++ = abs(n % 10) + '0'; } while (n /= 10); // remove digit captured via integer division. Stop once number equals zero (no more digits left) if (sign < 0) *s++ = '-'; *s = '\0'; reverse(original); // once reversed, everything is in the correct order (send original pointer to reverse function) } // chapter 3 itoa, exercise 3-6: handles minimum field width and converts n to characters in s which is width wide (padded with zeros if less than) void itoa3(int n, char *s, int width) { int sign; char *original = s; // keep original pointer location sign = n; do { *s++ = abs(n % 10) + '0'; } while (n /= 10); // remove digit captured via integer division. Stop once number equals zero (no more digits left) if (sign < 0) *s++ = '-'; while (s - original < width) *s++ = '0'; *s = '\0'; reverse(original); // once reversed, everything is in the correct order (send original pointer to reverse function) } // chapter 4 itoa, exercise 4-12, recursive itoa: uses static variables and converts n to characters in s. No longer needs reverse function void itoa4(int n, char *s) { static int i = 0, num = 0; // static is so i and num are the same variable each time itoa4 is called instead of being initialized as new ones num++; // keep track of number of recursive calls if (n < 0) { *(s + i++) = '-'; n = -n; // this does not support the INT_MIN value } if (n / 10) // if there are any digits left (n / 10 == 0 if n < 10), get them itoa4(n / 10, s); *(s + i++) = n % 10 + '0'; // adds digits in correct order since this is called in reverse order due to recursion num--; // decrement number of recursive calls if (num == 0) // if all recursive calls have finished, terminate string and reset i { *(s + i) = '\0'; i = 0; } } // chapter 3 reverse, page 62: reverse string s in place void reverse(char *s) { for (char *i = s, *j = s + (strlen(s) - 1); j - i > 0; i++, j--) // note char *i = s, *j = ... in for loop is same as declaring them like char *i, *j; above the for loop { int c = *i; *i = *j; *j = c; } } // chapter 4 strindex, page 69, return index of t in s, -1 if none int strindex(char *s, char *t) { char *sOriginal = s, *tOriginal = t, *u; for (s = sOriginal; *s != '\0'; s++) { for (u = s, t = tOriginal; *t != '\0' && *u == *t; u++, t++) ; if (t - tOriginal > 0 && *t == '\0') return s - sOriginal; } return -1; } // chapter 4 getop, page 78, gets next operator or numeric operand (for the reverse Polish calculator program) int getop(char *s) { int c; while ((*s = c = getch()) == ' ' || c == '\t') ; *(s + 1) = '\0'; if (!isdigit(c) && c != '.') return c; // not a number if (isdigit(c)) // collect integer part while (isdigit(*++s = c = getch())) ; if (c == '.') // collect fraction part while (isdigit(*++s = c = getch())) ; *s = '\0'; if (c != EOF) ungetch(c); return NUMBER; } // chapter 4 getch, page 79 (unmodified): get a (possibly pushed back) character int getch(void) { return (bufp > 0) ? buf[--bufp] : getchar(); } // chapter 4 ungetch, page 79 (unmodified): push character back on input void ungetch(int c) { if (bufp >= BUFSIZE) printf("ungetch: too many characters\n"); else buf[bufp++] = c; }
