Parsing equations from stdin

Question

The program should read equations from stdin, parse them and generate a matrix of the coefficient which represents the system.

Example:

$ ./eqs
x + y = 4
-y + 4x = 2

  1   1   4 
  4  -1   2

As you can see, the user can input as many equations they want and the program stops reading when an empty line is sent.

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

#define _M(i, j) (M->elements[(i) * M->cols + (j)])
#define ROWS 10
#define CHUNK 32

typedef struct {
    size_t rows;
    size_t cols;
    double *elements;
} Matrix;

void print_matrix(Matrix *);
Matrix *parse_input();
Matrix *create_matrix(size_t, size_t);
void free_matrix(Matrix *);
int readline(char **, size_t *, FILE *);
void memory_error(void);


int main(void) {
    Matrix *M = parse_input();
    print_matrix(M);
    free_matrix(M);
    return 0;
}


void print_matrix(Matrix *M) {
    size_t i, j;
    for (i = 0; i < M->rows; i++) {
        for (j = 0; j < M->cols; j++) {
            printf("%3g ", _M(i, j));
        }
        printf("\n");
    }
    printf("\n");
}


Matrix *parse_input() {
    char *row;
    size_t reading_size = CHUNK;
    if (!(row = malloc(reading_size))) memory_error();
    double coeff;
    size_t i, j, k, numrows = ROWS;
    double **unknowns;
    if (!(unknowns = malloc(numrows * sizeof(*unknowns)))) {
        free(row);
        memory_error();
    }
    for (i = 0 ; i < numrows; i++) {
        if (!(unknowns[i] = calloc(27, sizeof(**unknowns)))) {
            free(unknowns);
            memory_error();
        }
    }
    i = 0;
    do {
        if (i == numrows) {
            numrows *= 2;
            for (j = i + 1; j < numrows; j++) {
                if (!(unknowns[j] = calloc(27, sizeof(**unknowns)))) {
                    free(unknowns);
                    memory_error();
                }
            }
        }
        readline(&row, &reading_size, stdin);
        char *p = row;
        unsigned char past_equal = 0;
        coeff = 1;
        while (*p) {
            if (*p == '-') {
                coeff *= -1;
                p++;
            } else if (*p == '=') {
                past_equal = 1;
                p++;
            } else if (isdigit(*p)) {
                double val = strtod(p, &p);
                if (!past_equal) coeff *= val;
                else {
                    unknowns[i][26] = val;
                    break;
                }
            } else if (isalpha(*p)) {
                unknowns[i][tolower(*p++) - 'a'] = coeff;
                coeff = 1;
            } else p++;
        }
        i++;
    } while (row[0] != '\0');
    free(row);
    i--;
    unsigned short int nonzero_unknowns[27] = {0};
    nonzero_unknowns[26] = 1;
    for (j = 0; j < i; j++) {
        for (k = 0; k < 26; k++) {
            if (unknowns[j][k]) nonzero_unknowns[k] = 1;
        }
    }
    size_t ncols = 0;
    unsigned short int positions[26];
    for (j = 0; j < 26; j++) {
        if (nonzero_unknowns[j]) {
            positions[ncols++] = j;
        }
    }
    ncols++;
    if (i + 1 < ncols) {
        for (j = 0; j < i; j++) {
            free(unknowns[j]);
        }
        free(unknowns);
        puts("The system is underdetermined.");
        exit(EXIT_SUCCESS);
    }
    Matrix *M = create_matrix(i, ncols);
    for (j = 0; j < i; j++) {
        for (k = 0; k + 1 < ncols; k++) {
            _M(j, k) = unknowns[j][positions[k]];
        }
        _M(j, k) = unknowns[j][26];
    }
    for (j = 0; j < i; j++) {
        free(unknowns[j]);
    }
    free(unknowns);
    return M;
}


Matrix *create_matrix(size_t rows, size_t cols) {
    Matrix *M;
    if (!(M = malloc(sizeof *M))) memory_error();
    M->rows = rows;
    M->cols = cols;
    if (!(M->elements = calloc(rows * cols, sizeof(double)))) {
        free(M);
        memory_error();
    }
    return M;
}


void free_matrix(Matrix *M) {
    free(M->elements);
    free(M);
}


int readline(char **input, size_t *size, FILE *file) {
    char *offset;
    char *p;
    size_t old_size;

    // Already at the end of file
    if (!fgets(*input, *size, file)) {
        return EOF;
    }

    // Check if input already contains a newline
    if ((p = strchr(*input, '\n'))) {
        *p = 0;
        return 0;
    }

    do {
        old_size = *size;
        *size *= 2;
        if (!(*input = realloc(*input, *size))) {
            free(*input);
            memory_error();
        }
        offset = &((*input)[old_size - 1]);
    } while (fgets(offset, old_size + 1, file) &&
             offset[strlen(offset) - 1] != '\n');
    return 0;
}


void memory_error(void) {
    puts("Could not allocate memory.");
    exit(EXIT_FAILURE);
}

The parsing function is far too large, and it's quite complicated. Here's how the parsing is done:

• a line is read;
• the coefficients are put into the unknowns double array, which is 27 doubles wide to hold the 26 coefficients for the lowercase letters and the free term on the RHS of the equation;
• since an equation may not contain all the coefficients (some of them can be zero), the nonzero_unknowns holds the count;
• the matrix is initialized and returned.

I think the parse_input() function can definitely be broken up into multiple pieces, but I'm having a hard time simplifying it.

Answer 1

Here are some things that may help you improve your code.

Consider using parser generator tools

If I were writing code like this, I would use flex and bison (or equivalently lex and yacc). There are many resources available for these tools. Here is one such resource.

Eliminate "magic numbers"

Instead of hard-coding the constants 26 and 27 in the code, it would be better to use a #define or const and name them.

Fix memory leaks

In the case that there is, say, a single line as input, the program leaks memory. This is because the unknowns[i] or unknowns[j] allocates more than enough space, but the loop at the bottom of parse_input only frees i rows. Better would be to use a separate variable to track the actual number of allocated unknowns and then use that to drive the loop that frees them.

Don't bother allocating more memory than needed

There is no benefit to allocating more unknowns than needed. You could simply add them one at a time as needed, since you're allocating them one at a time in a loop anyway. Just make sure to keep track of the number of allocations so that you can correctly free the memory later.

Consider using streamlining error handling

Much of the code does error checking for malloc and then handles the result by freeing memory and then calling memory_error() which calls exit(). This is all good practice -- you are well ahead of the pack by actually carefully checking to make sure that the memory allocation suceeeded. That's great, and I would encourage you to continue this excellent habit. However, it clutters up the code quite a bit. An alternative approach would be to create a wrapper function for malloc and calloc that would enter the address into a flexible data structure. Then you could have a corresponding free_all that would free all allocated memory that could be called either in main or in memory_error. This could be done automatically if you register the function with atexit().

Break apart the parse_input function

Your description of the parse_input function points the way to how you might break apart the overly-long parse_input function. You could have one function that would create and return the unknowns structure. Then another to parse those into the matrix.

Minimize redundant loops

The nonzero_unknowns array could actually instead be the first row of the unknowns array. That way, you would reduce the number of variables (there are a lot!) and would be able to tally the unknown count as the parsing is done, making things much more efficient.

Consider handling malformed input lines

If the user types the line x - 4 = y the program incorrectly parses this as 1 -4 0. Another problem occurs if the user types in x - x = 0. It would be better, I think, to issue a warning to the user or, if you can, perform the algebra to correctly interpret the equation.

Eliminate return 0 at the end of main

For a long time now, the C language says that finishing main will implicitly generate the equivalent to return 0. For that reason, you should eliminate that line from your code.