calculator

#include <stdio.h>
#include <string.h>
#include <malloc.h>

typedef struct list {
    struct list *next;
    enum {
        OP,
        VAL
    } type;
    union {
        char c;
        long long v;
    };
} list;

int isempty(list *s) {
    return s->next == NULL;
}

list *new_list(unsigned char type) {
    list *new = malloc(sizeof(list));
    new->type = type;
    new->next = NULL;
    return new;
}

list *push(list *s, char c, long long v) {
    if (s == NULL) {
        return NULL;
    }
    list *new = malloc(sizeof(list));
    new->next = s;
    if (s->type == OP) {
        new->type = OP;
        new->c = c;
        return new;
    } else {
        new->type = VAL;
        new->v = v;
        return new;
    }
}

list *pop(list *s) {
    if (s == NULL) return NULL;
    if (s->next == NULL) {
        free(s);
        return NULL;
    } else {
        list *new = s->next;
        free(s);
        return new;
    }
}

static inline int isnum(char c) {
    return c >= '0' && c <= '9';
}

static inline int isop(char c) {
    return c == '*' || c == '/' || c == '+' || c == '-' || c == '(' || c == ')';
}

int prio(char c) {
    if (c == '(')
        return 0;
    if (c == '+' || c == '-')
        return 1;
    if (c == '*' || c == '/')
        return 2;
    return -1;
}

long long makeop(long long a, long long b, char c) {
    if (c == '+') {
        return a + b;
    }
    if (c == '-') {
        return a - b;
    }
    if (c == '*') {
        return a*b;
    }
    if (c == '/') {
        return a/b;
    }
    return 0;
}

int main(void) {
    list *op = new_list(0);
    list *nums = new_list(1);
    long long accum = 0;
    char *str = "1-(2+3)*2-2*(1+1)/2";
    int i = 0;
    while (str[i] != '\0') {
        if (isnum(str[i])) {
            while (isnum(str[i]) && str[i] != '\0') {
                accum *= 10;
                accum += str[i++] - '0';
            }
            nums = push(nums, 0, accum);
            accum = 0;
        } else if (isop(str[i])) {
            if (str[i] == '(') {
                op = push(op, '(', 0);
                i++;
            } else if (str[i] == ')') {
                while (op->c != '(') {
                    long long a, b;
                    b = nums->v;
                    nums = pop(nums);
                    a = nums->v;
                    nums = pop(nums);
                    long long c = makeop(a, b, op->c);
                    op = pop(op);
                    nums = push(nums, 0, c);
                }
                op = pop(op);
                i++;
            } else if (isempty(op) || prio(str[i]) > prio(op->c)) {
                op = push(op, str[i++], 0);
            } else {
                while (!isempty(op) && prio(str[i]) <= prio(op->c)) {
                    long long a, b;
                    b = nums->v;
                    nums = pop(nums);
                    a = nums->v;
                    nums = pop(nums);
                    long long c = makeop(a, b, op->c);
                    op = pop(op);
                    nums = push(nums, 0, c);
                }
                op = push(op, str[i++], 0);
            }
        }
    }
    while (!isempty(op)) {
        long long a, b;
        b = nums->v;
        nums = pop(nums);
        a = nums->v;
        nums = pop(nums);
        long long c = makeop(a, b, op->c);
        op = pop(op);
        nums = push(nums, 0, c);
    }
    long long res = nums->v;
    printf("%lld", res);
    free(op);
    while (nums) {
        nums = pop(nums);
    }
}