Calculator parsing S-expressions

Question

The following program is supposed to be a (command line) calculator that parses expression following syntax similar to Lisp's S-expressions.

Some examples:

$ echo "(+ 5 5)" | ./a.out

10.000000

$ echo "(+ (- 3 2) (* 9 2))" | ./a.out

19.000000

$ echo "(/ 24 6 2)" | ./a.out

2.000000

$ echo "(/ 24 (/ 6 2))" | ./a.out

8.000000

• The program is not supposed to deal with error handling (invalid S-expr, division by zero, ...). We assume the input is always valid. (The program is meant as an exercise and is not going to production).

• Separators can be space, tabs or newline characters.

• The only operations considered are +, -, *, /

• The program is supposed to deal with integers and float input.

Here's my headers file:

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define NUMBER '0'
#define OPERATOR '+'
#define MAX_NUM_SIZE 100
#define MAX_DEPTH 100
typedef double (*doublefun_t) ();
double add (double a, double b) { return a+b;}
double sub (double a, double b) { return a-b;}
double mul (double a, double b) { return a*b;}
double dvs (double a, double b) { return a/b;}
typedef struct args args_t;
struct args {
 double value;
 args_t *next;
};
typedef struct sexpr sexpr_t;
struct sexpr {
 char operation;
 args_t *arguments;
};
 
sexpr_t sstack[MAX_DEPTH];
 /*
 Initial value is -1 because the stack is empty.
 Will be incremented to 0 by the first opening paren.
 */
int current_level = -1;
double final_result = 0;
int getop(char s[]);
void create_sexpr();
void add_operation(char op);
void add_argument(double a);
void evaluate_sexpr();

And the actual code:

int main(int argc, char *argv[])
{
 int type;
 char s[MAX_NUM_SIZE];
 while ((type = tokenize(s)) != EOF) {
 switch(type) {
 case '(':
 create_sexpr();
 break;
 case OPERATOR:
 add_operation(s[0]);
 break;
 case NUMBER:
 add_argument(atof(s));
 break;
 case ')':
 evaluate_sexpr();
 break;
 default: break; /* Purposfully ignoring error handling */
 }
 if (current_level < 0)
 break;
 }
 printf("%f\n", final_result);
 
 return 0;
}
/*
 Parses input from stdin.
 returns NUMBERS for numbers or ascii value for any of ( ) + - * /
*/
int tokenize(char s[])
{
 int c;
 static int buf = EOF;
 if (isalnum(buf)) {
 c = buf;
 buf = EOF;
 return c;
 }
 
 if (buf == EOF || buf == ' ' || buf == '\t') 
 while ((*s = c = getchar()) == ' ' || c == '\t')
 ;
 else 
 *s = c = buf;
 buf = EOF;
 *(s + 1) = '0円';
 if (c == 42 || c == 43 || c == 45 || c == 47)
 return OPERATOR;
 
 if (!isdigit(c) && c != '.')
 return c; /* not a number */
 if (isdigit(c)) /* collect integer part */
 while (isdigit(*++s = c = getchar()))
 ;
 if (c == '.') /* collect fraction part */
 while (isdigit(*++s = c = getchar()))
 ;
 *s++ = '0円';
 buf = c;
 return NUMBER;
}
/*
 Create new sexpr and put it on the sstack.
 increment current_level index
*/
void create_sexpr()
{
 sexpr_t *new = malloc(sizeof(sexpr_t));
 new->arguments = NULL;
 sstack[++current_level] = *new;
}
void add_operation(char op)
{
 sstack[current_level].operation = op;
}
void add_argument(double a)
{
 args_t *new_argument = malloc(sizeof(args_t));
 args_t *args_iterator = sstack[current_level].arguments;
 
 new_argument->value = a;
 new_argument->next = NULL;
 if (args_iterator == NULL)
 sstack[current_level].arguments = new_argument;
 
 else {
 while (args_iterator->next != NULL)
 args_iterator = args_iterator->next;
 args_iterator->next=new_argument;
 }
}
void evaluate_sexpr()
{
 char op = sstack[current_level].operation;
 doublefun_t f = NULL;
 /* variable holders used for the accumulation
 */
 double a, b;
 args_t *new_argument = NULL;
 args_t *args_iterator = sstack[current_level].arguments;
 a = args_iterator->value;
 switch(op) {
 case '+':
 f = &add;
 break;
 case '-':
 f = &sub;
 break;
 case '*':
 f = &mul;
 break;
 case '/':
 f = &dvs;
 break;
 }
 
 while (args_iterator->next) {
 b = args_iterator->next->value;
 a = (*f)(a, b);
 args_iterator = args_iterator->next;
 }
 if (--current_level >= 0) {
 new_argument = malloc(sizeof(args_t));
 new_argument->value = a;
 new_argument->next = NULL;
 if (sstack[current_level].arguments == NULL) {
 sstack[current_level].arguments = new_argument;
 } else {
 args_iterator = sstack[current_level].arguments;
 while (args_iterator->next != NULL)
 args_iterator = args_iterator->next;
 args_iterator->next= new_argument;
 }
 }
 else {
 final_result = a;
 }
}

I would like to know how to improve the readability of the code, how to make it easier for other programmers to pick it up and understand it.

I am notably unsure about my use of function pointers. It's literally the first time I've ever used them (although it was pretty trivial).

Of course, any general remark about my coding style would be highly appreciated.

Answer 1

I don't know why nobody commented on this question as there is lots to be said. I'll go through what I found from the top down:

Your typedef for the functions should be complete with the types of call parameters. The name doublefun_t is the operation to be performed, so the word 'operation' might be approriate. Also the suffix _t is reserved by POSIX so is best avoided. I prefer to upper-case the first letter of types:

typedef double (*Operation) (double, double);
typedef struct arg Arg;
typedef struct sexpr Sexpr;

Functions and global variables should be static wherever possible - here that means everything at global scope except main. this does not really matter for single-file programs but it is best to get used to defaulting to static for bigger programs where it can improve optimization possibilities and reduce name-space pollution.

I would call your expression stack simply stack. The current_level variable, which indicates the level of the stack, would be better if the name identified its connection to the stack, eg stack_level. You could alternatively put these two variables into a structure to keep them together. Note that using globals such as these is not generally considered to be good practice. Normally variables are defined local to a function and passed around as call parameters. Globals are an easy alternative that rapidly become an unsupportable mess in larger programs. Your final_result is a case where a global is definitely unnecessary (return a value from evaluate_sexpr instead).

Put main at the end to avoid the need for prototypes of local functions. Also your functions without parameters should have ` void parameter list:

static void create_sexpr(void)

Your function tokenize would be more naturally named get_token (as it gets a token from stdin). It is also rather a mess. Firstly, note that you can push a character back into stdin using ungetc(). Using this you can avoid the need for a static variable to hold the last-read character between calls. Some other issues with the function are:

• repeated space-test conditions:

  if (buf == EOF || buf == ' ' || buf == '\t')
   while ((*s = c = getchar()) == ' ' || c == '\t')
   ;
  

  note that isspace is often better than explicit tests for characters

• embedded numeric constants

  if (c == 42 || c == 43 || c == 45 || c == 47)
   return OPERATOR;
  

  (use '+', '-', '*', '/' instead of the numbers)

• your double assignments are better avoided:

  while (isdigit(*++s = c = getchar()))
  

  note that s has type char while c has the type int so a cast would be better here anyway.

• there is no check for overflowing the output buffer

Your function create_sexpr is wrong. It allocates a new expression structure and then assigns that new struct to the existing stack variable:

void create_sexpr()
{
 sexpr_t *new = malloc(sizeof(sexpr_t));
 new->arguments = NULL;
 sstack[++current_level] = *new;
}

Notice the '*' in the the assignment on the last line. The malloced memory just gets leaked on return from the function. As the stack is preassigned (it is a static array), all the function needs to do is:

static void create_sexpr(void)
{
 stack[++stack_level].arguments = NULL;
}

Function evaluate_sexpr can be improved in a number of ways. For a start, as indicated above, it should return the expression value, not set a global result. Your use of function pointers is correct but the syntax can be simplified. you don't need to take the address of a function and you don't need to de-reference a function pointer. So with a function pointer f of type doublefun_t, instead of:

f = &add;
...
a = (*f)(a, b);

You can write simply:

f = add;
...
a = (*f)(a, b);

I would also extract the switch that determines the necessary function into a separate function returning a function pointer:

typedef double (*Operation) (double, double);
static Operation get_operation(int op)
{
 switch(op) {
 case '+': return add;
 case '-': return sub;
 case '*': return mul;
 case '/': return dvs;
 }
 return NULL;
}

And note that the code segment enclosed in the condition:

if (--current_level >= 0) {
 new_argument = malloc(sizeof(args_t));
 new_argument->value = a;
 new_argument->next = NULL;
 if (sstack[current_level].arguments == NULL) {
 sstack[current_level].arguments = new_argument;
 } else {
 args_iterator = sstack[current_level].arguments;
 while (args_iterator->next != NULL)
 args_iterator = args_iterator->next;
 args_iterator->next= new_argument;
 }
}

is exactly the same as calling your add_argument(a)

I hope there is something above that you can use.