#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>
#define NELEMS(arr) (sizeof arr / sizeof *arr)
#define NCOLS 26
#define NROWS 99
typedef long INT;
#define INTP "%ld"
#define INTSP "%ld"
typedef double REAL;
#define REALP "%g"
#define REALSP "%lf"
#define REALPOW pow
enum { SEL_REAL, SEL_INT, SEL_STRING, SEL_FORMULA, SEL_EVAL };
struct cell
{
int select;
REAL Vreal;
INT Vint;
char *Vstring;
};
struct cell empty = {SEL_INT, 0, 0, "<empty>"}, *EMPTY = ∅
/* Completely free a cell. */
void kill(struct cell *C);
/* Completely evaluate a formula. */
struct cell *eval(char *formula);
/* Helper functions that recursively parse a string. */
struct cell *eval_top(char *expr, int *idx);
struct cell *eval_term(char *expr, int *idx);
struct cell *eval_fact(char *expr, int *idx);
struct cell *eval_atom(char *expr, int *idx);
/* Helper functions that perform specific low-level operations. */
struct cell *eval_plus(struct cell *v1, struct cell *v2);
struct cell *eval_minus(struct cell *v1, struct cell *v2);
struct cell *eval_times(struct cell *v1, struct cell *v2);
struct cell *eval_slash(struct cell *v1, struct cell *v2);
struct cell *eval_caret(struct cell *v1, struct cell *v2);
/* Create and return a new cell; make a deep copy of 'Vs'. */
struct cell *new_cell(int select, INT Vi, REAL Vr, char *Vs);
/* Produce a visual representation of this cell. */
char *display(struct cell *C, char *buffer, size_t len);
/* Print to the screen visual representations of these cells. */
void view_cell(struct cell *C, size_t width);
void view_col(int col, int row);
void view_row(int col, int row);
/* The standard format for dumping a single cell to view. */
void dump_cell(int col, int row);
/* Input a new cell from the user and return it. */
struct cell *input(int select, const char *line);
/* Allocate a new string and input it from the user. */
char *allocate_input(char **buffer);
/* Return a cell. Called as "get_cell('A',25)" */
struct cell *get_cell(int col, int row);
/* Add a new cell. Called as "put_cell('A',25,cell)" */
void put_cell(int col, int row, struct cell *C);
/* The main loop. */
void run(void);
void show_help(int verbose);
struct cell *new_cell(int select, INT Vi, REAL Vr, char *Vs)
{
struct cell *C = malloc(sizeof *C);
if (C == NULL) return NULL;
C->select = select;
C->Vint = Vi;
C->Vreal = Vr;
if (Vs == NULL)
C->Vstring = NULL;
else {
C->Vstring = malloc(strlen(Vs)+1);
if (C->Vstring == NULL) { free(C); return NULL; }
strcpy(C->Vstring, Vs);
}
return C;
}
void kill(struct cell *C)
{
if (C == NULL) return;
if (C == EMPTY) return;
switch (C->select) {
case SEL_REAL:
case SEL_INT:
break;
case SEL_STRING:
case SEL_FORMULA:
case SEL_EVAL:
free(C->Vstring);
}
free(C);
}
char *display(struct cell *C, char *buffer, size_t len)
{
if (C == EMPTY) {
snprintf(buffer, len, "(empty)");
return buffer;
}
else if (C == NULL) {
snprintf(buffer, len, "(null)");
return buffer;
}
switch (C->select)
{
case SEL_REAL: {
snprintf(buffer, len, REALP, C->Vreal);
break;
}
case SEL_INT: {
int rc = snprintf(buffer, len, INTP, C->Vint);
if ((size_t)rc > len) {
INT mask = 1;
size_t i;
for (i=0; i < len-4; ++i)
mask *= 10;
snprintf(buffer, len, "..."INTP, C->Vint % mask);
}
break;
}
case SEL_STRING: {
size_t slen = strlen(C->Vstring);
if (slen+2 < len)
snprintf(buffer, len, "\"%s\"", C->Vstring);
else
snprintf(buffer, len, "\"%*s...", (int)(len-4), C->Vstring);
break;
}
case SEL_FORMULA: {
size_t slen = strlen(C->Vstring);
if (slen+1 < len)
snprintf(buffer, len, "=%s", C->Vstring);
else
snprintf(buffer, len, "=%*s...", (int)(len-4), C->Vstring);
break;
}
case SEL_EVAL: {
struct cell *v = eval(C->Vstring);
display(v, buffer, len);
kill(v);
return buffer;
}
}
return buffer;
}
void view_cell(struct cell *C, size_t width)
{
char buffer[width];
display(C, buffer, width);
fputs(buffer, stdout);
}
void view_col(int col, int row)
{
int i = (row < 4)? 1: (row-2);
int max = (row > NROWS-4)? NROWS: (row+3);
for (; i < max; ++i) {
dump_cell(col, i);
}
}
void view_row(int col, int row)
{
char cols[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
char *cp = strchr(cols, toupper(col));
printf("%c%d: ", col, row);
if (cp == NULL)
puts("Bad column!");
else {
int icol = cp-cols + 1;
int i = (icol < 4)? 1: (icol-2);
int max = (icol > NCOLS-4)? NCOLS: (icol+3);
for (; i < max; ++i) {
view_cell(get_cell(cols[i-1], row), 10);
fputs(" ", stdout);
}
putchar('\n');
}
}
struct cell *input(int select, const char *line)
{
struct cell *C = malloc(sizeof *C);
if (C == NULL) { puts("Out of memory!"); return NULL; }
switch (select)
{
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9': {
C->select = SEL_INT;
sscanf(line, INTSP, &C->Vint);
break;
}
case '\"': {
C->select = SEL_STRING;
break;
}
case '#': {
C->select = SEL_REAL;
sscanf(line, REALSP, &C->Vreal);
break;
}
case '=': {
C->select = SEL_FORMULA;
break;
}
case '*': {
C->select = SEL_EVAL;
break;
}
default: puts("Bad input! Eek!");
}
if (C->select == SEL_STRING || C->select == SEL_FORMULA
|| C->select == SEL_EVAL)
{
C->Vstring = malloc(strlen(line)+1);
if (C->Vstring == NULL) {
kill(C);
return NULL;
}
strcpy(C->Vstring, line);
}
return C;
}
char *allocate_input(char **buffer)
{
char *p = malloc(1);
size_t len = 0;
size_t max = 0;
int k;
if (p == NULL) return NULL;
while ((k = getchar()) != EOF && k != '\n')
{
if (len >= max) {
void *tmp = realloc(p, 2*max+4);
if (tmp == NULL) {
free(p);
return NULL;
}
p = tmp;
max = 2*max+3;
}
p[len++] = k;
}
p[len++] = '\0';
return (*buffer = p);
}
/*
Evaluation of formulas.
We support the following operations on integers and reals:
+ addition
- subtraction
* multiplication
/ division
^ exponentiation
Any operation for which one operand is a real, produces a real.
Division and exponentiation always produce reals.
We support the following operations on strings:
+ concatenation
* repetition
One of the operands to the repetition operator * must be an integer
or a real; the other one must be a string.
Cells are noted by [column][row] notation, as: A1, G42.
Any cell containing a formula will have that formula evaluated;
formulas are not treated as literal strings. That is, if the
cell A1 contains the formula =A2, and A2 contains #3.14, then
evaluating a cell with formula =A1 will yield the real #3.14.
Only integers are allowed as literal constants: 42, 16384.
All operations are infix, with the following precedence:
high (^) (*,/) (+,-) low
Braces () can be used to change the order of operations in an
expression.
*/
struct cell *eval(char *formula)
{
int idx = 0;
struct cell *C = eval_top(formula, &idx);
if (formula[idx] == '\0')
return C;
kill(C);
return NULL;
}
struct cell *eval_top(char *expr, int *idx)
{
struct cell *v1 = eval_term(expr, idx);
while (expr[*idx] && strchr("+-", expr[*idx])) {
struct cell *v2;
int op = expr[(*idx)++];
v2 = eval_term(expr, idx);
if (v2 == NULL) { kill(v1); return NULL; }
if (v2 == EMPTY) { kill(v1); return EMPTY; }
v1 = (op == '+')? eval_plus(v1, v2): eval_minus(v1, v2);
}
return v1;
}
struct cell *eval_term(char *expr, int *idx)
{
struct cell *v1 = eval_fact(expr, idx);
while (expr[*idx] && strchr("*/", expr[*idx])) {
struct cell *v2;
int op = expr[(*idx)++];
v2 = eval_fact(expr, idx);
if (v2 == NULL) { kill(v1); return NULL; }
if (v2 == EMPTY) { kill(v1); return EMPTY; }
v1 = (op == '*')? eval_times(v1, v2): eval_slash(v1, v2);
}
return v1;
}
struct cell *eval_fact(char *expr, int *idx)
{
struct cell *v1 = eval_atom(expr, idx);
if (v1 == NULL || v1 == EMPTY) return NULL;
if (expr[*idx] == '^') {
struct cell *v2;
++(*idx);
v2 = eval_fact(expr, idx);
if (v2 == NULL) { kill(v1); return NULL; }
if (v2 == EMPTY) { kill(v1); return EMPTY; }
v1 = eval_caret(v1, v2);
}
return v1;
}
struct cell *eval_atom(char *expr, int *idx)
{
if (isdigit(expr[*idx]) || (expr[*idx] == '-')) {
/* We have a literal integer. */
INT v = 0;
int sign = (expr[*idx] == '-')? (++(*idx), -1): +1;
while (isdigit(expr[*idx])) {
v = 10*v + expr[*idx]-'0';
++(*idx);
}
return new_cell(SEL_INT, sign*v, 0, NULL);
}
else if (isalpha(expr[*idx])) {
/* We have a cell reference. */
struct cell *C;
int col = toupper(expr[(*idx)++]);
int row = 0;
while (isdigit(expr[*idx])) {
row = 10*row + expr[*idx]-'0';
++(*idx);
}
C = get_cell(col, row);
if (C == NULL) return NULL;
if (C == EMPTY) return EMPTY;
if (C->select == SEL_FORMULA || C->select == SEL_EVAL)
return eval(C->Vstring);
return new_cell(C->select, C->Vint, C->Vreal, C->Vstring);
}
else if (expr[*idx] == '(') {
struct cell *v;
++(*idx);
v = eval_top(expr, idx);
if (expr[*idx] != ')') { kill(v); return NULL; }
++(*idx);
return v;
}
else if (expr[*idx] == '$') {
struct cell *v;
++(*idx);
v = eval_atom(expr, idx);
if (v == NULL) return NULL;
if (v == EMPTY) return new_cell(SEL_STRING, 0, 0, "(empty)");
switch (v->select) {
case SEL_INT:
v->Vstring = malloc(100);
if (v->Vstring == NULL) { kill(v); return NULL; }
snprintf(v->Vstring, 100, INTP, v->Vint);
break;
case SEL_REAL:
v->Vstring = malloc(100);
if (v->Vstring == NULL) { kill(v); return NULL; }
snprintf(v->Vstring, 100, REALP, v->Vreal);
break;
}
v->select = SEL_STRING;
return v;
}
else {
/* What is this? It's not a formula! */
return NULL;
}
}
struct cell *eval_caret(struct cell *v1, struct cell *v2)
{
REAL r1, r2;
if (v1->select == SEL_INT) r1 = v1->Vint;
else if (v1->select == SEL_REAL) r1 = v1->Vreal;
else { kill(v1); kill(v2); return NULL; }
if (v2->select == SEL_INT) r2 = v2->Vint;
else if (v2->select == SEL_REAL) r2 = v2->Vreal;
else { kill(v1); kill(v2); return NULL; }
kill(v1); kill(v2);
return new_cell(SEL_REAL, 0, REALPOW(r1, r2), NULL);
}
struct cell *eval_slash(struct cell *v1, struct cell *v2)
{
REAL r1, r2;
if (v1->select == SEL_INT) r1 = v1->Vint;
else if (v1->select == SEL_REAL) r1 = v1->Vreal;
else { kill(v1); kill(v2); return NULL; }
if (v2->select == SEL_INT) r2 = v2->Vint;
else if (v2->select == SEL_REAL) r2 = v2->Vreal;
else { kill(v1); kill(v2); return NULL; }
kill(v1); kill(v2);
return new_cell(SEL_REAL, 0, r1/r2, NULL);
}
struct cell *eval_times(struct cell *v1, struct cell *v2)
{
if (v1->select == SEL_STRING) {
INT count;
int i;
int v1slen = strlen(v1->Vstring);
struct cell *C;
if (v2->select == SEL_REAL)
count = v2->Vreal;
else if (v2->select == SEL_INT)
count = v2->Vint;
else { kill(v1); kill(v2); return NULL; }
C = new_cell(SEL_STRING, 0, 0, NULL);
if (C == NULL) { kill(v1); kill(v2); return NULL; }
C->Vstring = malloc(count*v1slen+1);
if (C->Vstring == NULL) {
kill(v1); kill(v2); kill(C);
return NULL;
}
for (i=0; count--; i += v1slen)
strcpy(C->Vstring+i, v1->Vstring);
kill(v1); kill(v2);
return C;
}
else if (v2->select == SEL_STRING) {
return eval_times(v2, v1);
}
else if (v1->select == SEL_INT && v2->select == SEL_INT) {
INT i1 = v1->Vint;
INT i2 = v2->Vint;
kill(v1); kill(v2);
return new_cell(SEL_INT, i1*i2, 0, NULL);
}
else {
REAL r1, r2;
if (v1->select == SEL_INT) r1 = v1->Vint;
else if (v1->select == SEL_REAL) r1 = v1->Vreal;
else { kill(v1); kill(v2); return NULL; }
if (v2->select == SEL_INT) r2 = v2->Vint;
else if (v2->select == SEL_REAL) r2 = v2->Vreal;
else { kill(v1); kill(v2); return NULL; }
kill(v1); kill(v2);
return new_cell(SEL_REAL, 0, r1*r2, NULL);
}
}
struct cell *eval_plus(struct cell *v1, struct cell *v2)
{
if (v1->select == SEL_STRING && v2->select == SEL_STRING) {
struct cell *C = new_cell(SEL_STRING, 0, 0, NULL);
if (C == NULL) { kill(v1); kill(v2); return NULL; }
C->Vstring = malloc(strlen(v1->Vstring)+strlen(v2->Vstring)+1);
if (C->Vstring == NULL) {
kill(v1); kill(v2); kill(C);
return NULL;
}
sprintf(C->Vstring, "%s%s", v1->Vstring, v2->Vstring);
kill(v1); kill(v2);
return C;
}
else if (v1->select == SEL_INT && v2->select == SEL_INT) {
INT i1 = v1->Vint;
INT i2 = v2->Vint;
kill(v1); kill(v2);
return new_cell(SEL_INT, i1+i2, 0, NULL);
}
else {
REAL r1, r2;
if (v1->select == SEL_INT) r1 = v1->Vint;
else if (v1->select == SEL_REAL) r1 = v1->Vreal;
else { kill(v1); kill(v2); return NULL; }
if (v2->select == SEL_INT) r2 = v2->Vint;
else if (v2->select == SEL_REAL) r2 = v2->Vreal;
else { kill(v1); kill(v2); return NULL; }
kill(v1); kill(v2);
return new_cell(SEL_REAL, 0, r1+r2, NULL);
}
}
struct cell *eval_minus(struct cell *v1, struct cell *v2)
{
if (v1->select == SEL_INT && v2->select == SEL_INT) {
INT i1 = v1->Vint;
INT i2 = v2->Vint;
kill(v1); kill(v2);
return new_cell(SEL_INT, i1-i2, 0, NULL);
}
else {
REAL r1, r2;
if (v1->select == SEL_INT) r1 = v1->Vint;
else if (v1->select == SEL_REAL) r1 = v1->Vreal;
else { kill(v1); kill(v2); return NULL; }
if (v2->select == SEL_INT) r2 = v2->Vint;
else if (v2->select == SEL_REAL) r2 = v2->Vreal;
else { kill(v1); kill(v2); return NULL; }
kill(v1); kill(v2);
return new_cell(SEL_REAL, 0, r1-r2, NULL);
}
}
/*
The actual spreadsheet particulars.
*/
static struct cell *spreadsheet[NCOLS][NROWS];
struct cell *get_cell(int col, int row)
{
struct cell *C;
char cols[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
char *cp = strchr(cols, toupper(col));
if (cp == NULL || row < 1 || row >= NROWS)
return NULL;
C = spreadsheet[cp-cols][row-1];
return (C == NULL)? EMPTY: C;
}
void put_cell(int col, int row, struct cell *C)
{
char cols[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
char *cp = strchr(cols, toupper(col));
if (cp != NULL) {
kill(spreadsheet[cp-cols][row-1]);
spreadsheet[cp-cols][row-1] = C;
}
}
void dump_cell(int col, int row)
{
printf("%c%d: ", toupper(col), row);
view_cell(get_cell(col, row), 70);
putchar('\n');
}
void run(void)
{
int col = 'A';
int row = 1;
char *line = NULL;
show_help(0);
for(; allocate_input(&line) != NULL; )
{
char *p = line;
int command;
if (line[0] == '\0') {
show_help(1);
free(line);
continue;
}
while (isspace(*p)) ++p;
if (isalpha(*p)) {
/* We have a cell reference! */
int newcol = toupper(*p++);
int newrow = 0;
for (; isdigit(*p); ++p)
newrow = 10*newrow + *p-'0';
if (1 <= newrow && newrow <= NROWS) {
col = newcol;
row = newrow;
}
else {
printf("Invalid cell reference %c%d.\n", newcol, newrow);
show_help(0);
}
while (isspace(*p)) ++p;
if (*p == '\0') {
/* User entered only a reference, or nothing at all. */
dump_cell(col, row);
free(line);
continue;
}
}
/* We have a command now. */
command = *p++;
switch (command) {
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9': {
struct cell *C = input('0', p-1);
if (C != NULL)
put_cell(col, row, C);
dump_cell(col, row);
break;
}
case '#': case '\"': {
struct cell *C = input(command, p);
if (C != NULL)
put_cell(col, row, C);
dump_cell(col, row);
break;
}
case '=': {
if (*p != '\0') {
struct cell *C = input(command, p);
if (C != NULL)
put_cell(col, row, C);
}
dump_cell(col, row);
break;
}
case '*': {
if (*p != '\0') {
struct cell *C = input(command, p);
if (C != NULL)
put_cell(col, row, C);
dump_cell(col, row);
}
else {
struct cell *C = get_cell(col, row);
printf("%c%d: ", col, row);
if (C && C->select == SEL_FORMULA) {
struct cell *E = eval(C->Vstring);
view_cell(E, 70);
kill(E);
}
else
view_cell(C, 70);
putchar('\n');
}
break;
}
case '-': {
view_row(col, row);
break;
}
case '|': {
view_col(col, row);
break;
}
case ':': {
printf("active: %c%d\n", col, row);
break;
}
case '?': {
struct cell *C = get_cell(col, row);
if (C && C->select == SEL_EVAL)
C->select = SEL_FORMULA;
else if (C && C->select == SEL_FORMULA)
C->select = SEL_EVAL;
dump_cell(col, row);
break;
}
case '$': {
struct cell *C = get_cell(col, row);
if (C && C->select == SEL_EVAL)
C->select = SEL_STRING;
else if (C && C->select == SEL_FORMULA)
C->select = SEL_STRING;
else if (C && C->select == SEL_STRING)
C->select = SEL_FORMULA;
dump_cell(col, row);
break;
}
case '.': {
/* Bind: evaluate this cell permanently. */
struct cell *C = get_cell(col, row);
if (C && C->select == SEL_EVAL)
put_cell(col, row, eval(C->Vstring));
else if (C && C->select == SEL_FORMULA)
put_cell(col, row, eval(C->Vstring));
dump_cell(col, row);
break;
}
case '!': {
put_cell(col, row, NULL);
dump_cell(col, row);
break;
}
case '@': {
/* Quit. */
return;
}
default: {
/* Just treat the input like a string. */
struct cell *C;
if ((C = input('\"', p-1)) != NULL)
put_cell(col, row, C);
dump_cell(col, row);
break;
}
}
free(line);
}
}
void show_help(int verbose)
{
if (verbose) goto verbose;
puts("Ready for input.");
puts("[cellnames] [command] [newvalue] [separator]");
puts("G42 :=*|-?$.! \"x =x *x #x ;");
puts("Enter @ to quit.");
return;
verbose:
puts("Use the following commands to enter data into the spreadsheet:");
puts(" A1 make A1 the currently active cell");
puts(" 1234 enter an integer into the named cell");
puts(" #3.14 enter a real number");
puts(" hello enter a string");
puts(" \"#314 enter a string beginning with a command character");
puts(" =A2^4+3 enter a FORMULA to be displayed as a string");
puts(" *A2^4+3 enter an EVAL formula to be displayed evaluated");
puts("Use the following commands to manipulate the spreadsheet:");
puts(" : view the name of the currently active cell");
puts(" = view the contents of the active cell");
puts(" - view the contents of the active row");
puts(" | view the contents of the active column");
puts(" * evaluate the contents of the active cell");
puts(" ? convert the active cell between FORMULA and EVAL");
puts(" $ convert the active cell between FORMULA and STRING");
puts(" . permanently bind the value of the active cell");
puts(" ! delete the active cell");
puts("Formulas may contain the infix operators +-*/^(),");
puts("cell references, integer literals, and the prefix operator $,");
puts("which converts any cell to its string representation.");
return;
}
int main(void)
{
size_t i, j;
run();
for (i=0; i < NELEMS(spreadsheet); ++i)
for (j=0; j < NELEMS(spreadsheet[i]); ++j)
kill(spreadsheet[i][j]);
return EXIT_SUCCESS;
}