6
\$\begingroup\$

This is a simple arithmetic calculator, which parses mathematical expressions specified in infix notation using the shunting-yard algorithm. This 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:

$ calc <arith_expr>

This is an example of running the calculator:

$ calc "3^2 + 4 * (2 - 1)"

The passed arithmetic expression is tokenized and the operands and operators are stored in two different stacks, implemented as linked lists. The calculator currently supports these operators + - * / ^.

In calc.c I have:

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

#include "stack.h"

struct node_float *operands = NULL;
struct node_char *operators = NULL;

enum token_type {
    TOKEN_TYPE_OPERATOR,
    TOKEN_TYPE_OPERAND,
};

/* Can store an operator or an operand */
struct token {
    enum token_type type;
    union {
        char operator;
        float operand;
    } data;
};

/* Return precedence of a given operator */
int prec(char op)
{
    switch (op) {
    case '+':
    case '-':
        return 2;
    case '*':
    case '/':
        return 3;
    case '^':
        return 4;
    default:
        fprintf(stderr, "Error in %s: invalid operator '%c'\n",
                __func__, op);
        exit(EXIT_FAILURE);
    }
}

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

/* Apply mathematical operation to top two elements on the stack */
float eval(char op)
{
    float tmp = pop_float(&operands);
    switch (op) {
    case '+':
        return pop_float(&operands) + tmp;
    case '-':
        return pop_float(&operands) - tmp;
    case '*':
        return pop_float(&operands) * tmp;
    case '/':
        return pop_float(&operands) / tmp;
    case '^':
        return pow(pop_float(&operands), tmp);
    default:
        fprintf(stderr, "Error in %s: invalid operator '%c'\n",
                __func__, op);
        exit(EXIT_FAILURE);
    }
}

/* 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) {
        fprintf(stderr, "Error in %s: memory allocation failed\n", __func__);
        exit(EXIT_FAILURE);
    }

    if (op_allowed && is_operator(*expr[0])) {
        token->type = TOKEN_TYPE_OPERATOR;
        token->data.operator = *expr[0];
        ++(*expr);
        op_allowed = false;
    } else if (!op_allowed && *expr[0] == '(') {
        token->type = TOKEN_TYPE_OPERATOR;
        token->data.operator = *expr[0];
        ++(*expr);
    } else if (op_allowed && *expr[0] == ')') {
        token->type = TOKEN_TYPE_OPERATOR;
        token->data.operator = *expr[0];
        ++(*expr);
    } else {
        token->type = TOKEN_TYPE_OPERAND;
        char *rest;
        token->data.operand = strtof(*expr, &rest);
        if (*expr == rest) {
            fprintf(stderr, "Error in %s: invalid expression\n", __func__);
            exit(EXIT_FAILURE);
        }
        strcpy(*expr, rest);
        op_allowed = true;
    }

    return token;
}

/* Handle a given token, which might be an operand or an operator */
void handle_token(struct token *token)
{
    if (token->type == TOKEN_TYPE_OPERAND) {
        push_float(&operands, token->data.operand);
    } else if (is_operator(token->data.operator)) {
        while (operators != NULL && operators->data != '(' &&
            prec(token->data.operator) <= prec(operators->data)) {
            float result = eval(pop_char(&operators));
            push_float(&operands, result);
        }
        push_char(&operators, token->data.operator);
    } else if (token->data.operator == '(') {
        push_char(&operators, token->data.operator);
    } else if (token->data.operator == ')') {
        while (operators != NULL && operators->data != '(') {
            float result = eval(pop_char(&operators));
            push_float(&operands, result);
        }
        pop_char(&operators);
    } else {
        fprintf(stderr, "Error in %s: invalid operator '%c'\n",
                __func__, token->data.operator);
        exit(EXIT_FAILURE);
    }
}

/* 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]);
        return EXIT_FAILURE;
    }

    char *expr = argv[1];
    rmspaces(expr);
    struct token *token;
    while (expr[0] != '\0') {
        token = tokenize(&expr);
        handle_token(token);
    }
    free(token);

    while (operators != NULL) {
        float result = eval(pop_char(&operators));
        push_float(&operands, result);
    }
    if (operands == NULL || operands->next != NULL) {
        fprintf(stderr, "Error in %s: too many operands on stack\n", __func__);
        exit(EXIT_FAILURE);
    }

    printf("Result: %f\n", operands->data);
    return EXIT_SUCCESS;
}

In stack.c I have:

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

#include "stack.h"

/* Push float onto stack */
void push_float(struct node_float **head, float data)
{
    struct node_float *new = malloc(sizeof *new);
    if (!new) {
        fprintf(stderr, "Error in %s: memory allocation failed\n", __func__);
        exit(EXIT_FAILURE);
    }
    new->data = data;
    new->next = *head;
    *head = new;
}

/* Pop float from stack */
float pop_float(struct node_float **head)
{
    if (*head == NULL) {
        fprintf(stderr, "Error in %s: stack underflow\n", __func__);
        exit(EXIT_FAILURE);
    }
    struct node_float *tmp = *head;
    float data = tmp->data;
    *head = tmp->next;
    free(tmp);
    return data;
}

/* Push char onto stack */
void push_char(struct node_char **head, char data)
{
    struct node_char *new = malloc(sizeof *new);
    if (!new) {
        fprintf(stderr, "Error in %s: memory allocation failed\n", __func__);
        exit(EXIT_FAILURE);
    }
    new->data = data;
    new->next = *head;
    *head = new;
}

/* Pop char from stack */
char pop_char(struct node_char **head)
{
    if (*head == NULL) {
        fprintf(stderr, "Error in %s: stack underflow\n", __func__);
        exit(EXIT_FAILURE);
    }
    struct node_char *tmp = *head;
    char data = tmp->data;
    *head = tmp->next;
    free(tmp);
    return data;
}

In stack.h I have:

#ifndef STACK_H
#define STACK_H

struct node_float {
    float data;
    struct node_float *next;
};

struct node_char {
    char data;
    struct node_char *next;
};

/* Push float onto stack */
void push_float(struct node_float **head, float data);

/* Pop float from stack */
float pop_float(struct node_float **head);

/* Push char onto stack */
void push_char(struct node_char **head, char data);

/* Pop char from stack */
char pop_char(struct node_char **head);

#endif /* STACK_H */
\$\endgroup\$
1
  • \$\begingroup\$ Welcome to Stack Review and great first question. \$\endgroup\$ – dariosicily Mar 22 at 11:49
2
\$\begingroup\$

Keep the stack as simple as possible

You have given your stack implementation knowledge of the types that are stored in the stack; either float or char. This complicates the code, since now you have to have two node structs, and two sets of push and pop functions, one for each type. You should try to apply the separation of concerns design principle here, and limit the stack code to just managing the stack itself, not its contents.

In this case, I would do this by making the stack manage tokens, and let the calling code worry about whether a token holds a float or a char. For example, like so:

struct node {
    struct token data;
    struct node *next;
};

void push(struct node **head, struct token data);
struct token pop(struct node **head);

This will actually simplify other code as well. For example, instead of:

push_float(&operands, token->data.operand);

You can now just write:

push(&operands, *token);

And even a line like:

return pop_float(&operands) + tmp;

Can still be a one-liner, by writing:

return pop(&operands).data.operand + tmp;

Consider passing tokens by value everywhere

A struct token is a rather small structure, in fact on a 64-bit operating system it's just as big as a single pointer. So I would just pass it by value where possible, and avoid unnecessary memory allocations. This will also get rid of a memory leak, since you called free(token) outside the first while-loop in main().

Fix the example usage

If you just run ./calc without arguments, you print usage information, including an example. This is very nice! However, the example you print makes it look like your program wants the input in reverse polish notation, but your program actually expects infix notation. I would just copy the example you gave here on Code Review.

Move the code calling the tokenizer and evaluation function into its own function

Again, try to separate concerns, and let main() just worry about parsing the command line arguments and printing the final result, but move the code calling the tokenizer and evaluator into its own function. For example:

float calculate(char *expr) {
    rmspaces(expr);
    ...
    return operands->data.data.operand;
}

int main(int argc, char *argv[]) {
    if (argc != 2) {
        ...
    }

    printf("Result: %f\n", calculate(argv[1]));
}

Avoid static and global variables if possible

There are global variables operands and operators, and a static variable op_allowed in tokenize(). While it is fine for a simple application like this, in larger applications this can lead to problems. A good practice is to put all the state related to the calculator in a single struct, and pass a pointer to such a struct to any functions that need to access this state. For example:

struct calculator_state {
    struct node *operands;
    struct node *operators;
    bool op_allowed;
};

float calculate(char *expr) {
    rmspaces(expr);

    struct calculator_state state = {NULL, NULL, false};

    while (expr[0] != '\0') {
        struct token token = tokenize(&state, expr);
        handle_token(token);
    }

    ...
}

Of course you have to modify tokenize(), handle_token() and eval() to use this state as well:

float eval(struct calculator state &state, char op) {
    float tmp = pop(&state.operands);
    ...
}

Ensure you free all memory

At the end of the calculation, you have a single node left on the stack that contains the result. It is good practice to also ensure you free that node before returning from calculate(), otherwise you will have a memory leak. This is not a big deal in your current program, but if you were to use calculate() multiple times in a larger program, then it does become a problem.

Don't copy strings over themselves

There is a bug in this line of code:

strcpy(*expr, rest);

You are copying part of a string over itself. This has the same issues as memcpy() with overlapping source and destination: there is no guarantee in which order strcpy() is doing the actual copying, so it might corrupt parts of rest before it finishes the copy. There is no strmove() unfortunately, but you don't need it at all, you can just replace this line with:

*expr = rest;
\$\endgroup\$
0

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.