Shunting yard calculator in C

Question

I'm new to C, and made this program that parses a string expression into a linked list post-fix expression, and then evaluates it, without parsing the string beforehand. Wondering if there is anything to improve/fix (I feel like my implementation is kinda big...)

main.c

#include "util.h"
#include <ctype.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

Node *parse_to_postfix(char *expr);
long double evaluate_postfix(Node *expr, int *err);

int main(void) {
    char expr[200] = {0};

    while (1) {
        fgets(expr, 200, stdin);

        if (strncmp(expr, "quit", 4) == 0) {
            break;
        }

        Node *parsed = parse_to_postfix(expr);

        if (parsed != NULL) {
            int err;
            long double result = evaluate_postfix(parsed, &err);

            if (err == 0) {
                printf("= %Lf\n", result);
            }
        }
        memset(expr, 0, strlen(expr));
    }

    return 0;
}

Node *parse_to_postfix(char *expr) {
    Stack *output = stack_create(NULL);
    Stack *op_stack = stack_create(NULL);
    Node *bottom = NULL;
    int first_node_created = 0, previous_node_is_op = 1;
    char *num_buf = calloc(strlen(expr) + 1, sizeof(char));

    if (num_buf == NULL) {
        perror("error:");
        abort();
    }

    for (char c = *expr; c != 0; c = *++expr) {
        if (isspace(c)) {
            continue;
        }

        int c_is_op = is_operator(c);
        int converted_num = 0;

        // convert num_buf to long double and push to output
        if ((c_is_op || c == '(' || c == ')') && strlen(num_buf) > 0) {
            stack_push(output, node_create(strtold(num_buf, NULL), TYPE_NUMBER));
            memset(num_buf, 0, strlen(num_buf));
            converted_num = 1;
        }

        if (c_is_op) {
            // convert - into -1 *
            if (c == '-' &&
                ((op_stack->top != NULL &&
                  (previous_node_is_op || (op_stack->top->value_type == TYPE_PAREN && !converted_num))) ||
                 output->top == NULL)) {
                c = '*';
                stack_push(output, node_create(-1, TYPE_NUMBER));

                // simulate having -1 * take precedence over right associative operators
                if (node_check_valuetype(op_stack->top, TYPE_OPERATOR) &&
                    !is_left_assoc(op_stack->top->operator)) {

                    stack_push(op_stack, node_create(c, TYPE_OPERATOR)); // push * to op_stack
                    goto exit_ifs;
                }
            }

            while (node_check_valuetype(op_stack->top, TYPE_OPERATOR) &&
                   ((is_left_assoc(c) && get_precedence(c) <= get_precedence(op_stack->top->operator)) ||
                    (!is_left_assoc(c) && get_precedence(c) < get_precedence(op_stack->top->operator)))) {

                stack_push(output, stack_pop(op_stack)); // pop from stack to output
            }
            stack_push(op_stack, node_create(c, TYPE_OPERATOR)); // push c to op_stack
        } else if (c == '(') {
            stack_push(op_stack, node_create(c, TYPE_PAREN));
        } else if (c == ')') {
            while (!node_check_valuetype(op_stack->top, TYPE_PAREN) && op_stack->top->paren != '(') {
                stack_push(output, stack_pop(op_stack)); // pop from stack to output
            }
            free(stack_pop(op_stack)); // free left parenthesis
        } else {
            num_buf[strlen(num_buf)] = c;
        }

    exit_ifs:
        // set reference to first node added to output
        if (!first_node_created && output->top != NULL) {
            bottom = output->top;
            first_node_created = 1;
        }

        previous_node_is_op = c_is_op;
    }

    // convert any left over digits in num_buf
    if (strlen(num_buf) > 0) {
        stack_push(output, node_create(strtold(num_buf, NULL), TYPE_NUMBER));
    }

    // pop remaining operators in op_stack to output
    while (op_stack->top != NULL) {
        stack_push(output, stack_pop(op_stack));
    }

    if (!first_node_created && output->top != NULL) {
        bottom = output->top;
    }

    stack_free(op_stack);
    free(output);
    free(num_buf);

    // debugging purposes
    // Node *head = bottom;
   
    // while (head != NULL) {
    //     node_print(head, 0);
    //     head = head->previous;
    // }
    // printf("\n");

    return bottom;
}

long double evaluate_postfix(Node *expr, int *err) {
    Stack *stack = stack_create(NULL);
    Node *previous = expr->previous;

    *err = 0;

    while (expr != NULL) {
        previous = expr->previous;

        if (node_check_valuetype(expr, TYPE_NUMBER)) {
            stack_push(stack, node_remove(expr));
        } else if (node_check_valuetype(expr, TYPE_OPERATOR)) {
            if (stack->top == NULL || stack->top->next == NULL) {
                printf("error: syntax error\n");
                *err = 1;
                break;
            }

            Node *a = stack_pop(stack), *b = stack_pop(stack);
            long double result;

            switch (expr->operator) {
                case '+':
                    result = b->number + a->number;
                    break;
                case '-':
                    result = b->number - a->number;
                    break;
                case '/':
                    result = b->number / a->number;
                    break;
                case '*':
                    result = b->number * a->number;
                    break;
                case '^':
                    result = pow(b->number, a->number);
                    break;
            }
            free(a);
            free(b);
            free(node_remove(expr)); // free operator from expression
            stack_push(stack, node_create(result, TYPE_NUMBER));
        }
        expr = previous;
    }
    long double whole_result = (node_check_valuetype(stack->top, TYPE_NUMBER)) ? stack->top->number : 0;

    stack_free(stack);
    node_free(expr);

    return whole_result;
}

util.c

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

void node_print(Node *target, int newline) {
    if (target == NULL) {
        printf("cannot print NULL node\n");
        return;
    }
    char nl = (newline) ? '\n' : ' ';
    switch (target->value_type) {
        case TYPE_NUMBER:
            printf("%Lf%c", target->number, nl);
            break;
        case TYPE_OPERATOR:
            printf("%c%c", target->operator, nl);
            break;
        case TYPE_PAREN:
            printf("%c%c", target->paren, nl);
            break;
        default:
            printf("node has no declared value type\n");
    }
}

Node *node_create(long double value, enum NodeType type) {
    Node *new = malloc(sizeof(*new));

    if (new == NULL) {
        perror("error:");
        abort();
    }

    new->next = NULL;
    new->previous = NULL;

    switch (type) {
        case TYPE_NUMBER:
            new->number = value;
            break;
        case TYPE_OPERATOR:
            new->operator=(char) value;
            break;
        case TYPE_PAREN:
            new->paren = (char)value;
            break;
        default:
            printf("error: no matching NodeType\n");
            return NULL;
    }
    new->value_type = type;

    return new;
}

Node *node_insert(Node *target, Node *previous, Node *next) {
    if (previous != NULL) {
        previous->next = target;
    }
    if (next != NULL) {
        next->previous = target;
    }
    target->previous = previous;
    target->next = next;

    return target;
}

Node *node_remove(Node *target) {
    if (target == NULL) {
        printf("error: cannot remove NULL node\n");
        return NULL;
    }
    Node *previous = target->previous, *next = target->next;

    if (previous != NULL) {
        previous->next = next;
    }
    if (next != NULL) {
        next->previous = previous;
    }
    target->next = NULL;
    target->previous = NULL;

    return target;
}

void node_free(Node *target) {
    if (target != NULL) {
        Node *prev_target = target->previous;

        while (target != NULL) {
            Node *next = target->next;
            free(target);
            target = next;
        }

        target = prev_target;
        while (target != NULL) {
            Node *previous = target->previous;
            free(target);
            target = previous;
        }
    }
}

Stack *stack_create(Node *head) {
    Stack *new = malloc(sizeof(*new));

    if (new == NULL) {
        perror("error:");
        abort();
    }
    new->top = head;

    return new;
}

void stack_free(Stack *target) {
    if (target != NULL) {
        node_free(target->top);
    }
    free(target);
}

Node *stack_push(Stack *target, Node *node) {
    if (target != NULL) {
        if (node == NULL) {
            printf("error: cannot push NULL node to stack\n");
            return NULL;
        }
        Node *prev_top = target->top;

        target->top = node;
        node_insert(node, NULL, prev_top);

        return node;
    } else {
        printf("error: cannot push on undeclared Stack\n");
        return NULL;
    }
}

Node *stack_pop(Stack *target) {
    if (target != NULL) {
        Node *top = target->top;

        if (top == NULL) {
            printf("error: cannot pop NULL node from stack\n");
            return NULL;
        }

        Node *new_top = top->next;
        Node *popped = node_remove(top);

        target->top = new_top;
        return popped;

    } else {
        printf("error: cannot pop on undeclared Stack\n");
        return NULL;
    }
}

int is_operator(char target) {
    switch (target) {
        case '+':
            break;
        case '-':
            break;
        case '/':
            break;
        case '*':
            break;
        case '^':
            break;
        default:
            return 0;
    }
    return 1;
}

int get_precedence(char operator) {
    switch (operator) {
        case '+':
            return 1;
        case '-':
            return 1;
        case '/':
            return 2;
        case '*':
            return 2;
        case '^':
            return 3;
        default:
            printf("error: cannot get precendence of unknown operator '%c'\n", operator);
            return 0;
    }
}

int is_left_assoc(char operator) {
    switch (operator) {
        case '+':
            return 1;
        case '-':
            return 1;
        case '/':
            return 1;
        case '*':
            return 1;
        case '^':
            return 0;
        default:
            printf("error: cannot get associativity of unknown operator '%c'\n", operator);
            return 0;
    }
}

int node_check_valuetype(Node *target, enum NodeType type) {
    return (target == NULL || target->value_type != type) ? 0 : 1;
}

util.h

#ifndef INCLUDE_UTIL_H
#define INCLUDE_UTIL_H

enum NodeType { TYPE_OPERATOR, TYPE_NUMBER, TYPE_PAREN};

typedef struct Node {
    struct Node *next;
    struct Node *previous;
    union {
        char operator;
        char paren;
        long double number;
    };
    enum NodeType value_type;
} Node;

typedef struct Stack {
    Node *top;
} Stack;

// print value of node
void node_print(Node *target, int newline);

//  allocate node
Node *node_create(long double value, enum NodeType type);

// insert node between two nodes
Node *node_insert(Node *target, Node *previous, Node *next);

// update surrounding nodes and return popped node
Node *node_remove(Node *target);

// free all nodes that are connected to target
void node_free(Node *target);

// free all nodes and stack
void stack_free(Stack *target);

// allocate new stack
Stack *stack_create(Node *head);

// push node to stack
Node *stack_push(Stack *target, Node *node);

// pop node from stack
Node *stack_pop(Stack *target);

// if char is an operator * / + - ^
int is_operator(char target);

// get precendence value of operator
int get_precedence(char operator);

// return 1 if operator is left associative
int is_left_assoc(char operator);

// check if node matches type, return 0 when NULL
int node_check_valuetype(Node *target, enum NodeType type);

#endif

I compiled them using these gcc flags:

gcc 13.2.1:
-Wall -Wextra -Wpedantic -std=c17 -g -lm

Answer 1

Expanding on the idea of an array for the stack, the Node type wouldn't need to hold pointers and you wouldn't have to allocate a Node on the heap. This would eliminate much of the memory management, such as this bit:

free(a);
free(b);
free(node_remove(expr));

---

I would rather have something like Error evaluate_postfix(Node *expr, long double *result) rather than returning the error via pointer. Although, I'd much prefer parse_to_postfix to check for syntax errors instead.

---

evaluate_postfix shouldn't consume *expr. You wouldn't expect a function with that kind of a name to have side-effects. main() owns expr so it should be responsible for freeing it.

---

parse_to_postfix is too complex. Much of the complexity comes from handling the unary minus. I think you could better handle it by treating it as a part of the following number. If the previous token is anything but a number or ), then - is unary and you could put it into num_buf.

I would also separate the parsing of numbers into its own function. Instead of pushing digits to num_buf, you'd call parse_number(&expr) when you encounter a digit (or a unary minus or some other number character), which would consume all following digits (and other bits of a number) from the input and return the number's value. In fact, strtold would do this for you.

---

What happens if parentheses don't match in the input? Particularly if there's no ( before ), it seems your code would produce a very non-informative error message: error: cannot push NULL node to stack.

Answer 2

while (1) {
    fgets(expr, 200, stdin);
    ...
}

What happens if fgets() fail? You are ignoring its return value.

---

if (strncmp(expr, "quit", 4) == 0) {
    break;
}

There's no way I'd have known to enter quit to exit had I not read the source code.

---

memset(expr, 0, strlen(expr));

What's the point of setting expr to all zero bytes when it is just going to be overwritten and null-terminated by fgets()?

---

Node *parse_to_postfix(char *expr);

We wouldn't require this forward declaration if we define parse_to_postfix() before main().

---

char *num_buf = calloc(strlen(expr) + 1, sizeof(char));

sizeof(char) is defined by the standard to be 1. You can safely elide it.

---

if (num_buf == NULL) {
    perror("error:");
    abort();
}

There's no need to cause an abnormal termination here. Simply do exit(EXIT_FAILURE).

---

if (isspace(c)) {
    continue;
}

isspace() expects an unsigned char, not a char.

---

Stack *output = stack_create(NULL);
Stack *op_stack = stack_create(NULL);

The return values go unchecked. Why return a null pointer on malloc() failure if you were simply going to ignore it?

---

You are computing the length of num_buf thrice in parse_to_postfix(). Consider using an extra variable to save the length.

---

// debugging purposes
// Node *head = bottom;
   
// while (head != NULL) {
//     node_print(head, 0);
//     head = head->previous;
// }
// printf("\n");

This is no longer required.

---

printf("error: syntax error\n");

Error messages go to stderr, not stdout.

---

Node *a = stack_pop(stack), *b = stack_pop(stack);
long double result;

switch (expr->operator) {
    case '+':
        result = b->number + a->number;
        break;

The above would invoke undefined behavior if stack_pop() returns NULL.

---

case '/':
    result = b->number / a->number;

This would invoke undefined behavior if a->number was 0.

---

Node *parse_to_postfix(char *expr); 

parse_to_postfix() expects a non-null pointer, and it must be declared as such:

Node *parse_to_prefix(char expr[static 1]);

Same goes for the rest of the functions. This requires C99 albeit.

---

void node_print(Node *target, int newline) {
    if (target == NULL) {
        printf("cannot print NULL node\n");
        return;
    }
    char nl = (newline) ? '\n' : ' ';

newline only needs to denote two states here, so it should be of type bool. (Include stdbool.h prior for the definition of bool prior to C2X.)

The parentheses around newline are also unneeded.

---

Node *new = malloc(sizeof(*new));

new is a bad identifier name since it is a reserved keyword in C++. Even if you never care for porting/compatibility with C++, you should still avoid naming identifiers after keywords from that language, since IDE style formatting tends to have a "C/C++" setting and then it will format new in weird ways.

Note that you can drop the parentheses around *new.

---

if (target == NULL) {
    printf("error: cannot remove NULL node\n");
    return NULL;
}

Instead of printing an error message to stdout - which should really have been stderr - just return NULL. Nobody wants a library to print random stuff to stdout/stderr in their code, especially without their knowledge.

---

int is_operator(char target) {
    switch (target) {
        case '+':
            break;
        case '-':
            break;
        case '/':
            break;
        case '*':
            break;
        case '^':
            break;
        default:
            return 0;
    }
    return 1;
}

This over-engineered function can be simplified to:

return strchr("+-/*^", target) != NULL;

Or you could use memchr().

Or:

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

---

int get_precedence(char operator) {
    switch (operator) {
        case '+':
            return 1;
        case '-':
            return 1;
        case '/':
            return 2;
        case '*':
            return 2;
        case '^':
            return 3;
        default:
            printf("error: cannot get precendence of unknown operator '%c'\n", operator);
            return 0;
    }
}

You could use a map for this:

int get_precedence(char operator) {
    struct {
        const char op;
        const unsigned int precedence;
    } ops = {
        {'+', 1},
        {'-', 1},
        {'/', 2},
        {'*', 2},
        {...}
    };

But that might be overkill. Or you could merge cases:

case '+':
case '-':
    return 1;
case '/':
case '*':
    return 2;
case '*':
    return 3;
default:
    return 0;

---

int is_left_assoc(char operator) {
    switch (operator) {
        case '+':
            return 1;
        case '-':
            return 1;
        case '/':
            return 1;
        case '*':
            return 1;
        case '^':
            return 0;
        default:
            printf("error: cannot get associativity of unknown operator '%c'\n", operator);
            return 0;
    }
}

Same goes for this:

case '+': case '-': case '*': case '/':
    return 1;
default:
    return 0;

---

int node_check_valuetype(Node *target, enum NodeType type) {
    return (target == NULL || target->value_type != type) ? 0 : 1;
}

This can be simplified to:

    return target && target->value_type == type;

Some comments on the stack implementation:

I believe you have overly complicated it. Like @Davilsor suggests, a dynamic array with its top element at the end would have been more performant, more maintainable, and easier to implement. It would also have respected principle of locality.

I also do not like that stack's internals are known to the client, i.e. its definition is included in util.h. I would have expected it to be an opaque type, with get_top(), get_size() et cetera.

The functions that are internal to the implementation should be defined as having internal linkage, i.e. marked static in the translation unit, and their declarations should be removed from the corresponding header file.

Consider using a common prefix for all the symbols. Currently, you have stack_, node_, et cetera.

Answer 3

double math?

.number is a long double.

I'd expect result = pow(b->number, a->number); to generate a compiler warning. Save time and enable all compiler warnings and use powl() with long double arguments.

Better output choice

printf("%Lf%c", target->number, nl); can print many uninformative digits with larges values and simply zeros with small non-zero values. Better to use printf("%Lg%c", target->number, nl); which switches to exponential notation for large/tiny values.

Even better, use printf("%.*Lg%c", LDBL_DECIMAL_DIG, target->number, nl); to print useful significant digits.