Exercise 5.6 - Find the pattern using pointers¶
Question¶
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).
/**
*
* pattern matching program
*
**/
#include<stdio.h>
#include<ctype.h>
#include<string.h>
#include<stdlib.h>
#define NUMBER '0' /* signal that a number was found */
#define MAXVAL 100 /* maximum depth of val stack */
#define BUFSIZE 100
#define MAXLINE 1000
#define MAXOP 100
int getch(void);
void ungetch(int);
int getop(char *);
void push(double);
double pop(void);
int mgetline(char *s, int lim);
int strindex(char *s, char *t);
int atoiv2(char *);
void itoav2(int n, char *s);
void reverse(char *);
int sp = 0;
int bufp = 0;
double val[MAXVAL];
char buf[BUFSIZE];
char pattern[] = "ould"; /* pattern to search for */
/* find all the matching patterns */
int main(void) {
char line[MAXLINE];
int found = 0;
/* mgetline ends when a newline starts with X */
while ((mgetline(line, MAXLINE)) > 0)
if (strindex(line, pattern) >= 0) {
printf("%s\n", line);
found++;
}
char *s = "1234";
int ret;
ret = atoiv2(s);
printf("%d\n", ret);
char s1[100];
int i = 12345;
itoav2(i, s1);
reverse(s1);
printf("%s\n", s1);
char *s2 = "This is a line";
char *t = "is";
ret = 0;
ret = strindex(s2, t);
printf("%d\n", ret);
int type;
double op2;
char s3[MAXOP];
while ((type = getop(s3)) != EOF) {
switch (type) {
case NUMBER:
push(atof(s3));
break;
case '+':
push(pop() + pop());
break;
case '*':
push(pop() * pop());
break;
case '-':
op2 = pop();
push(pop() - op2);
break;
case '/':
op2 = pop();
if (op2 != 0.0)
push(pop() / op2);
else
printf("error: zero divisor\n");
break;
case '\n':
printf("\t%.8g\n", pop());
break;
default:
printf("error: unknown command %s\n", s);
break;
}
}
return 0;
}
int atoiv2(char *s) {
int n, sign;
for (; isspace(*s); s++) /* skip white space */
;
sign = (*s == '-') ? -1 : 1;
if (*s == '+' || *s == '-')
s++;
for (n = 0; isdigit(*s); s++)
n = 10 * n + *s - '0';
return sign * n;
}
/* reverse polish calculator */
/* push: push f onto value stack */
void push(double f) {
if (sp < MAXVAL)
val[sp++] = f;
else
printf("error: stack full,can't push %g\n", f);
}
/* pop: pop and return top value from stack */
double pop(void) {
if (sp > 0)
return val[--sp];
else {
printf("error: stack empty \n");
return 0.0;
}
}
/* getop: get next operator or numeric operand pointer version */
/* getop */
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))
while (isdigit(*++s = c = getch()));
if (c == '.')
while (isdigit(*++s = c = getch()));
*s = '\0';
if (c != EOF)
ungetch(c);
return NUMBER;
}
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;
}
/* itoa */
void itoav2(int n, char *s) {
int sign;
char *t = s;
if ((sign = n) < 0)
n = -n;
do {
*s++ = n % 10 + '0';
} while ((n /= 10) > 0);
if (sign < 0)
*s++ = '-';
*s = '\0';
}
/* reverse */
void reverse(char *s) {
int c;
char *t;
for (t = s + (strlen(s) - 1); s < t; s++, t--) {
c = *s;
*s = *t;
*t = c;
}
}
/* mgetline */
int mgetline(char *s, int lim) {
int c;
char *t = s;
while (--lim > 0 && (c = getchar()) != 'X' && c != '\n')
*s++ = c;
if (c == '\n')
*s++ = c;
*s = '\0';
return s - t;
}
/* strindex */
int strindex(char *s, char *t) {
char *b = s;
char *p, *r;
for (; *s != '\0'; s++) {
for (p = s, r = t; *r != '\0' && *p == *r; p++, r++);
if (r > t && *r == '\0')
return s - b;
}
return -1;
}
Explanation¶
_getline takes a string (char *) and MAXLINE, the maximum length of the line. It
gets one character at a time using getchar() and as long as we are under limit
(less than MAXLINE) and it is not n character. It stores the charaacters in the
line, advancing the pointer for each character.
When it hits n, it adds n and closes the line with 0. _getline returns the length of the line, subtracting the last address with initial address.
atoi - the gets the sign and then read each read each character using the pointer, checks if it is digit and converts it to integer. The curx of this function is:
for(n=0;isdigit(*s);s++)
n = 10 *n + *s - '0';
itoa - takes the number, converts it into a string, by adding ‘0’ and stores them to a character pointer, advancing the pointer after each assignment. When the assignments are done, it adds a null character to form a valid C string:
do
{
*s++ = n % 10 + '0';
} while ((n /= 10) > 0);
if(sign < 0)
*s++ = '-';
*s='\0';
reverse takes a char *s as argument and uses a temporary string char *t, to
swap the characters from the end to the front. It uses another intermediate
character c to do the swap.
strindex takes two strings char *s and char *t and determines the start of
the string t in s. It stores the s position in the base, b and then advances s
and for each advance checks if the substring t is contained in s. If the
substring is contained, it returns the current position - base position, that s
-b, otherwise it returns -1.
getop works by taking a char *s as it’s argument. It reads the character and
stores it in s. It skips the whitespaces and then checks if it isdigit.
If it not a digit, it closes the string using 0 and returns the character.
If it is digit, then it reads both real and decimal part, along with dot, closes the string using 0 and the returns that it found a NUMBER.
Since checking of the character, happens after reading, an extra character is read when our condition fails (that is we have completely read the NUMBER) In that case, we do a ungetch, to return the character back to buffer and return that we found a NUMBER.