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 is27
doubles wide to hold the26
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.