5
\$\begingroup\$

This program tokenizes an arithmetic expression specified in infix notation. It is one of my personal projects and I would love to receive expert advice.

After compiling, you can run the program with one command-line argument:

$ tokenize <arith_expr>

This is an example of running the program:

$ tokenize "3^2 + 4.5 * (-2 - 1)"

The tokenizer currently supports these operators + - * / ^.

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

/* Can store an operator or an operand */
struct token {
    char operator;
    float operand;
};

/* Check if given token is an operator */
bool is_operator(char token)
{
    if (token == '+' ||
        token == '-' ||
        token == '*' ||
        token == '/' ||
        token == '^')
        return true;
    else
        return false;
}

/* Remove all spaces from string */
void rmspaces(char *str)
{
    const char *dup = str;
    do {
        while (isspace(*dup))
            ++dup;
    } while (*str++ = *dup++);
}

/* Return first token of given arithmetic expression */
struct token *tokenize(char **expr)
{
    static bool op_allowed = false;
    struct token *token = malloc(sizeof *token);
    if (!token) {
        printf("Error: memory allocation failed");
        exit(EXIT_FAILURE);
    }

    if (op_allowed && is_operator(*expr[0])) {
        token->operator = *expr[0];
        ++(*expr);
        op_allowed = false;
    } else if (!op_allowed && *expr[0] == '(') {
        token->operator = *expr[0];
        ++(*expr);
    } else if (op_allowed && *expr[0] == ')') {
        token->operator = *expr[0];
        ++(*expr);
    } else {
        char *rest;
        token->operand = strtof(*expr, &rest);
        token->operator = '\0';
        if (*expr == rest) {
            printf("Invalid expression\n");
            exit(EXIT_FAILURE);
        }
        strcpy(*expr, rest);
        op_allowed = true;
    }

    return token;
}

/* Handle command line arguments */
int main(int argc, char *argv[])
{
    if (argc != 2) {
        printf("Usage:   %s <arith_expr>\n"
            "Example: %s \"5 2 3 * +\"\n",
            argv[0], argv[0]);
        exit(EXIT_FAILURE);
    }

    char *expr = argv[1];
    rmspaces(expr);
    struct token *token;
    while (expr[0] != '\0') {
        token = tokenize(&expr);
        if (token->operator == '\0') // token is operand
            printf("%f\n", token->operand);
        else
            printf("%c\n", token->operator);
    }

    return EXIT_SUCCESS;
}
\$\endgroup\$
4
\$\begingroup\$

Your is_operator function can be rewritten as

return token == '+' || token == '-' || token == '*' || token == '/' || token == '^';

Much cleaner, in my opinion.


The program has a memory leak. Your tokenize function allocates a struct token on the heap, but the object is never freed.

Better yet, instead of returning a struct token*, just return a struct token. The struct certainly isn't large enough to warrant an allocation on the heap.


Instead of checking whether token is an operand by comparing operator to 0, use an enum.

typedef enum { 
       TokenType_Operator, 
       TokenType_Operand 
} token_type;

Then your token struct can consist of the token_type enum, and an union.

struct token
{
   token_type type;
   union {
       char operator;
       float operand;
   } data;
};

If you're using C11, you don't even need to name the union anything.


As a next step, try to implement a tokenizer that tokenizes in one pass. Right now, your tokenizer 1) removes whitespace (which involves a linear pass) and 2) copies of the rest of the string after the tokenizing an operand into the original buffer. If you have a large buffer, this could become a bottleneck.

A common way to implement a tokenizer is using a DFA (deterministic finite automata). In fact, a DFA is a starting point for most handwritten lexers.

\$\endgroup\$
1
2
\$\begingroup\$
while (isspace(*dup))

has a common mistake, but it is wrong. For example Linux manuals have this in their notes:

NOTES The standards require that the argument c for these functions is either EOF or a value that is representable in the type unsigned char. If the argument c is of type char, it must be cast to unsigned char, as in the following example:

char c;
...
res = toupper((unsigned char) c);

This is necessary because char may be the equivalent of signed char, in which case a byte where the top bit is set would be sign extended when converting to int, yielding a value that is outside the range of unsigned char.


For isoperator I would use

return token && strchr("+-*/^", token);

strchr returns the pointer to the first occurrence of the given character in the string, and NULL pointer if not found. The token && part is to make sure that token is not the NUL character, because strchr does return a pointer to the terminator if 2nd argument is the NUL character.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks! I will take your suggestions into consideration. \$\endgroup\$ – Andy Sukowski-Bang Apr 5 at 12:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.