I set up this blog at the suggestion of some people, as a means of documenting my answers to C programming exercises. Since no one is reading the answers and commenting on them, I can't be stuffed continuing to blog my answers.
I hope these answers are of some use to someone, somewhere. Some of the programs contain minor bugs, so please don't rely on them as canonical answers.
Richard
Monday, August 29, 2011
Exercise 1-24
Exercise 1-24 Write a program to check a C program for rudimentary syntax errors like unbalanced parentheses, brackets and braces. Don't forget about quotes, both single and double, escape sequences, and comments. (This program is hard if you do it in full generality.)
#include <stdio.h>
#include <stdlib.h>
/* For simplicity, this program doesn't deal with this case:
'\'' */
enum states { NORMAL = 0, FORWARD_SLASH = 1, IN_COMMENT = 2,
CLOSING_ASTERISK = 3, IN_QUOTE = 4, ESCAPING = 5,
SINGLE_QUOTE = 6 };
int brackets = 0, parentheses = 0, braces = 0;
void print(int c)
{
if (c!=EOF)
putchar(c);
switch(c)
{
case '(':
parentheses++;
break;
case ')':
parentheses--;
break;
case '[':
brackets++;
break;
case ']':
brackets--;
break;
case '{':
braces++;
break;
case '}':
braces--;
break;
default:
break;
}
}
enum states single_quote(int c)
{
enum states state = SINGLE_QUOTE;
switch(c)
{
default:
state = SINGLE_QUOTE;
print(c);
break;
case '\'':
state = NORMAL;
print(c);
break;
}
return state;
}
enum states escaping(int c)
{
print(c); /* Regardless of what it is. */
return NORMAL;
}
enum states in_quote(int c)
{
enum states state = IN_QUOTE;
switch(c)
{
case '\"':
state = NORMAL;
break;
default:
state = IN_QUOTE;
break;
}
print(c);
return state;
}
enum states closing_asterisk(int c)
{
enum states state = IN_COMMENT;
switch(c)
{
case '/':
state = NORMAL;
break;
case '*':
state = CLOSING_ASTERISK;
break;
default:
state = IN_COMMENT;
break;
}
return state;
}
enum states in_comment(int c)
{
enum states state = IN_COMMENT;
switch(c)
{
case '*':
state = CLOSING_ASTERISK;
break;
default:
state = IN_COMMENT;
break;
}
return state;
}
enum states forward_slash(int c)
{
enum states state = NORMAL;
switch(c)
{
case '\'':
state = SINGLE_QUOTE;
break;
case '/':
print('/');
state = FORWARD_SLASH;
break;
case '*':
state = IN_COMMENT;
break;
default:
state = NORMAL;
print('/');
print(c);
break;
}
return state;
}
enum states normal(int c)
{
enum states state = NORMAL;
switch(c)
{
case '\'':
state = SINGLE_QUOTE;
print(c);
break;
case '\\':
state = ESCAPING;
print(c);
break;
case '\"':
state = IN_QUOTE;
print(c);
break;
case '/':
state = FORWARD_SLASH;
break;
default:
state = NORMAL;
print(c);
break;
}
return state;
}
enum states parse(int c, enum states state)
{
enum states return_state = NORMAL;
switch(state)
{
case SINGLE_QUOTE:
return_state = single_quote(c);
break;
case IN_QUOTE:
return_state = in_quote(c);
break;
case CLOSING_ASTERISK:
return_state = closing_asterisk(c);
break;
case IN_COMMENT:
return_state = in_comment(c);
break;
case FORWARD_SLASH:
return_state = forward_slash(c);
break;
case NORMAL:
default:
return_state = normal(c);
break;
}
return return_state;
}
int main(void)
{
enum states state = NORMAL;
int c;
do
state = parse(c = getchar(), state);
while (c!=EOF);
printf("\n");
if (parentheses)
printf("Unbalanced parentheses.\n");
if (brackets)
printf("Unbalanced brackets.\n");
if (braces)
printf("Unbalanced braces.\n");
if (!parentheses && !brackets && !braces)
printf("Looks good.\n");
return EXIT_SUCCESS;
}
Exercise 1-23 (continued)
Exercise 1-23 Write a program to remove all comments from a C program. Don't forget to handle quoted strings and character constants properly. C comments do not nest.
#include <stdio.h>
#include <stdlib.h>
/* For simplicity, this program doesn't deal with this case:
'\'' */
enum states { NORMAL = 0, FORWARD_SLASH = 1, IN_COMMENT = 2,
CLOSING_ASTERISK = 3, IN_QUOTE = 4, ESCAPING = 5,
SINGLE_QUOTE = 6 };
void print(int c)
{
if (c!=EOF)
putchar(c);
}
enum states single_quote(int c)
{
enum states state = SINGLE_QUOTE;
switch(c)
{
default:
state = SINGLE_QUOTE;
print(c);
break;
case '\'':
state = NORMAL;
print(c);
break;
}
return state;
}
enum states escaping(int c)
{
print(c); /* Regardless of what it is. */
return NORMAL;
}
enum states in_quote(int c)
{
enum states state = IN_QUOTE;
switch(c)
{
case '\"':
state = NORMAL;
break;
default:
state = IN_QUOTE;
break;
}
print(c);
return state;
}
enum states closing_asterisk(int c)
{
enum states state = IN_COMMENT;
switch(c)
{
case '/':
state = NORMAL;
break;
case '*':
state = CLOSING_ASTERISK;
break;
default:
state = IN_COMMENT;
break;
}
return state;
}
enum states in_comment(int c)
{
enum states state = IN_COMMENT;
switch(c)
{
case '*':
state = CLOSING_ASTERISK;
break;
default:
state = IN_COMMENT;
break;
}
return state;
}
enum states forward_slash(int c)
{
enum states state = NORMAL;
switch(c)
{
case '\'':
state = SINGLE_QUOTE;
break;
case '/':
print('/');
state = FORWARD_SLASH;
break;
case '*':
state = IN_COMMENT;
break;
default:
state = NORMAL;
print('/');
print(c);
break;
}
return state;
}
enum states normal(int c)
{
enum states state = NORMAL;
switch(c)
{
case '\'':
state = SINGLE_QUOTE;
print(c);
break;
case '\\':
state = ESCAPING;
print(c);
break;
case '\"':
state = IN_QUOTE;
print(c);
break;
case '/':
state = FORWARD_SLASH;
break;
default:
state = NORMAL;
print(c);
break;
}
return state;
}
enum states parse(int c, enum states state)
{
enum states return_state = NORMAL;
switch(state)
{
case SINGLE_QUOTE:
return_state = single_quote(c);
break;
case IN_QUOTE:
return_state = in_quote(c);
break;
case CLOSING_ASTERISK:
return_state = closing_asterisk(c);
break;
case IN_COMMENT:
return_state = in_comment(c);
break;
case FORWARD_SLASH:
return_state = forward_slash(c);
break;
case NORMAL:
default:
return_state = normal(c);
break;
}
return return_state;
}
int main(void)
{
enum states state = NORMAL;
int c;
do
state = parse(c = getchar(), state);
while (c!=EOF);
return EXIT_SUCCESS;
}
Sunday, August 28, 2011
Exercise 1-23 (continued)
Exercise 1-23 Write a program to remove all comments from a C program. Don't forget to handle quoted strings and character constants properly. C comments do not nest.
#include <stdio.h>
static int buffer_slash = 0;
void remove_comments(char current, char last)
{
static int comment = 0;
static int skip = 0;
if (skip)
skip = 0; /* Avoid what happens when you have / * / in sequence */
else if (comment == 0)
{
if (current == '/')
buffer_slash = 1;
else if (last == '/' && current == '*')
{
buffer_slash = 0;
comment = 1;
skip = 1;
}
else
{
if (buffer_slash)
{
buffer_slash = 0;
putchar('/');
}
putchar(current);
}
}
else /* comment == 1 */
{
if (last == '*' && current == '/')
comment = 0;
}
}
void remove_double_quotes(char current, char last)
{
static int quotes_open = 0;
if (quotes_open)
putchar(current);
else
remove_comments(current, last);
if (current=='\"')
quotes_open = !quotes_open;
}
void parse_single_quotes(char current, char last)
{
static int single_quote_open = 0;
/* If we're in single quotes, then " does not open a string literal. */
if (single_quote_open)
remove_comments(current, last);
else
remove_double_quotes(current, last);
if ((last!='\\') && (current=='\''))
single_quote_open = !single_quote_open;
}
int main(void)
{
int last = 0;
int current;
while (current = getchar(), current!=EOF)
{
parse_single_quotes(current, last);
last = current;
}
if (buffer_slash)
putchar('/');
return 0;
}
Exercise 1-23
Exercise 1-23 Write a program to remove all comments from a C program. Don't forget to handle quoted strings and character constants properly. C comments do not nest.
I used function pointers for this, which may not be the best solution.
I used function pointers for this, which may not be the best solution.
#include <stdio.h>
/* Function prototypes. */
void normal(char c);
void backslash(char c);
void open_slash(char c);
void in_comment(char c);
void close_asterisk(char c);
void in_double_quotes(char c);
void in_single_quotes(char c);
void backslash_double(char c);
void backslash_single(char c);
/* Our function pointer. */
void (*state)(char c);
void normal(char c)
{
if (c=='/')
state = open_slash;
else
{
if (c=='\'')
state = in_single_quotes;
else if (c=='\"')
state = in_double_quotes;
putchar(c);
}
}
void backslash_double(char c)
{
/* Ignore the next character. */
state = in_double_quotes;
}
void backslash_single(char c)
{
/* Ignore the next character. */
state = in_single_quotes;\
}
void open_slash(char c)
{
if (c=='*')
state = in_comment;
else if (c=='/')
putchar('/');
else
{
putchar('/');
putchar(c);
state = normal;
}
}
void in_comment(char c)
{
if (c=='*')
state = close_asterisk;
}
void close_asterisk(char c)
{
if (c=='/')
state = normal;
else if (c!='*')
state = in_comment;
/* else state = close_asterisk; */
}
void in_double_quotes(char c)
{
if (c=='"')
state = normal;
if (c=='\\')
state = backslash_double;
putchar(c);
}
void in_single_quotes(char c)
{
if (c=='\'')
state = normal;
if (c=='\\')
state = backslash_single;
putchar(c);
}
int main(void)
{
int c;
state = normal;
while (c = getchar(), c!=EOF)
(*state)(c);
/* We could warn the user about an unclosed comment,
* or single or double quotes. */
return 0;
}
Saturday, August 20, 2011
Exercise 1-22
Exercise 1-22 Write a program to ``fold'' long input lines into two or more shorter lines after the last non-blank character that occurs before the n-th column of input. Make sure your program does something intelligent with very long lines, and if there are no blanks or tabs before the specified column.
I have not been able to answer this exercise after 3 days of trying.
I have not been able to answer this exercise after 3 days of trying.
Thursday, August 18, 2011
Exercise 1-21
Exercise 1-21 Write a program entab that replaces strings of blanks by the minimum number of tabs and blanks to achieve the same spacing. Use the same tab stops as for detab. When either a tab or a single blank would suffice to reach a tab stop, which should be given preference?
I guess the answer to the latter part of the question is that I would work out what my priority is: compatibility of file format, need for WYSIWYG printing, performance in printing, performance in displaying on screen, etc. I would then make the decision accordingly.
I guess the answer to the latter part of the question is that I would work out what my priority is: compatibility of file format, need for WYSIWYG printing, performance in printing, performance in displaying on screen, etc. I would then make the decision accordingly.
#include <stdio.h>
#define TABSTOP 8
int column = 0;
static unsigned int blanks = 0;
void pushblank(void)
{
blanks++;
}
void popblanks(void)
{
unsigned int desired_column = column+blanks;
unsigned int desired_tabspace = desired_column / TABSTOP;
unsigned int present_tabspace = column / TABSTOP;
while (desired_tabspace > present_tabspace)
{
unsigned int blanks_consumed = ((present_tabspace+1) * TABSTOP) - column;
putchar('\t');
column+= blanks_consumed;
blanks-= blanks_consumed;
present_tabspace++;
}
while (blanks)
{
putchar(' ');
column++;
blanks--;
}
}
int main(void)
{
int c;
while (c=getchar(), c!=EOF)
switch(c)
{
case ' ':
pushblank();
break;
/* Should have cases for \r, \b and a few other things here too. */
case '\n':
column = 0;
putchar(c);
break;
default:
popblanks();
putchar(c);
column++;
break;
}
popblanks();
return 0;
}
Exercise 1-20
Exercise 1-20 Write a program detab that replaces tabs in the input with the proper number of blanks to space to the next tab stop. Assume a fixed set of tab stops, say every n columns. Should n be a variable or a symbolic parameter?
For clarity, I have renamed n to TABSTOP. If the value is known at compile time then a symbolic parameter seems appropriate. If it is not, then a variable is best. Perhaps the value could be given on the command line.
For clarity, I have renamed n to TABSTOP. If the value is known at compile time then a symbolic parameter seems appropriate. If it is not, then a variable is best. Perhaps the value could be given on the command line.
#include <stdio.h>
#define TABSTOP 8
int main(void)
{
int c;
int col = 0;
while (c = getchar(), c!=EOF)
{
switch(c)
{
/* Should also put \r here and a bunch of other cases. */
case '\n':
putchar(c);
col = 0;
break;
case '\t':
do
{
putchar(' ');
col++;
}
while(col%TABSTOP);
break;
default:
putchar(c);
col++;
break;
}
}
return 0;
}
Exercise 1-19 (continued)
Exercise 1-19 Write a function reverse(s) that reverses the character string s. Use it to write a program that reverses its input a line at a time.
Although this program does not satisfy the specification exactly, it does do the same job, much better than the program that does satisfy the specification exactly.
Although this program does not satisfy the specification exactly, it does do the same job, much better than the program that does satisfy the specification exactly.
#include <stdio.h>
int reverse(void)
{
int c = getchar();
int d;
if (c=='\n' || c==EOF)
return c;
d = reverse();
putchar(c);
return d;
}
int main(void)
{
while (reverse()=='\n')
putchar('\n');
return 0;
}
Exercise 1-19
Exercise 1-19 Write a function reverse(s) that reverses the character string s. Use it to write a program that reverses its input a line at a time.
I note that there may be better ways of writing a program that reverses its input (such as a recursive function), but this program satisfies the specification exactly.
I note that there may be better ways of writing a program that reverses its input (such as a recursive function), but this program satisfies the specification exactly.
#include <stdio.h>
#define LINELENGTH 100
int reverse(char *s)
{
char *end = s;
while (*end)
end++; /* end points to the null. */
end--;
while (end>s)
{
char temp;
temp = *end;
*end = *s;
*s = temp;
end--;
s++;
}
}
int main(void)
{
int c;
int bufpos = 0;
char buffer[LINELENGTH];
do
{
c = getchar();
switch(c)
{
case '\n':
buffer[bufpos] = 0;
reverse(buffer);
puts(buffer);
bufpos = 0;
break;
case EOF:
buffer[bufpos] = 0;
reverse(buffer);
printf("%s", buffer);
break;
default:
buffer[bufpos++] = c;
if (bufpos == LINELENGTH)
{
printf("Buffer overflow.\n");
return 1;
}
break;
}
}
while(c!=EOF);
return 0;
}
Wednesday, August 17, 2011
Exercise 1-18 (continued)
Exercise 1-18 Write a program to remove trailing blanks and tabs from each line of input, and to delete entirely blank lines.
This program uses dynamic memory allocation to store the blanks. Therefore, it will store any number of blanks until the computer runs out of memory. However, it will be far slower than the statically allocated versions.
This program uses dynamic memory allocation to store the blanks. Therefore, it will store any number of blanks until the computer runs out of memory. However, it will be far slower than the statically allocated versions.
#include <stdio.h>
#include <stdlib.h>
size_t buffer_size = 0;
char *buffer = NULL;
void clear_buffer(void)
{
free(buffer);
buffer = NULL;
buffer_size = 0;
}
void flush(void)
{
size_t i;
for (i = 0; i < buffer_size; ++i)
putchar(buffer[i]);
clear_buffer();
}
void push(char c)
{
void *newbuffer;
newbuffer = realloc(buffer, buffer_size+1);
if (newbuffer == NULL)
{
printf("Out of memory.\n");
free(buffer);
exit(1);
}
buffer = newbuffer;
buffer[buffer_size] = c;
buffer_size++;
}
void display(char c)
{
flush();
putchar(c);
}
void strip(char c)
{
switch(c)
{
case ' ':
case '\t':
push(c);
break;
case '\n':
clear_buffer();
putchar(c);
break;
default:
display(c);
break;
}
}
int main(void)
{
int c;
int newline = 1;
while (c=getchar(), c!=EOF)
{
if (!newline || c!='\n')
{
newline = 0;
strip(c);
}
if (c=='\n')
newline = 1;
}
clear_buffer();
return 0;
}
Exercise 1-18 (continued)
Exercise 1-18 Write a program to remove trailing blanks and tabs from each line of input, and to delete entirely blank lines.
This program can buffer up to a certain number of blank characters, and spills only one character at a time when the buffer is full.
This program can buffer up to a certain number of blank characters, and spills only one character at a time when the buffer is full.
#include <stdio.h>
#define BUFFERSIZE 100
int bufpos = 0;
char buffer[BUFFERSIZE];
void clear_buffer(void)
{
bufpos = 0;
}
void flush(void)
{
int i;
for (i = 0; i < bufpos; ++i)
putchar(buffer[i]);
clear_buffer();
}
void push(char c)
{
if (bufpos<BUFFERSIZE)
buffer[bufpos++] = c;
else
{
int i;
putchar(buffer[0]);
for (i=1; i<BUFFERSIZE; ++i)
buffer[i-1] = buffer[i];
buffer[BUFFERSIZE-1] = c;
}
}
void display(char c)
{
flush();
putchar(c);
}
void strip(char c)
{
switch(c)
{
case ' ':
case '\t':
push(c);
break;
case '\n':
clear_buffer();
putchar(c);
break;
default:
display(c);
break;
}
}
int main(void)
{
int c;
int newline = 1;
while (c=getchar(), c!=EOF)
{
if (!newline || c!='\n')
{
newline = 0;
strip(c);
}
if (c=='\n')
newline = 1;
}
return 0;
}
Subscribe to:
Posts (Atom)