validate if a sequence of push/pop is valid.

valid_train.c

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

bool check(int max, char *p)
{
    /* simulate the push/pop of stacks */
    bool *stack = (bool *)malloc((max+1) * sizeof(*stack));
    memset(stack, true, (max+1) * sizeof(*stack));

    bool valid = true;
    int top = *p - '0';
    stack[0] = false;
    stack[top] = false;
    p++;

    while (*p) {
        int index = *p - '0';

        if (top < index) {
            top = index;
        } else {
            for (; top > index; top--) {
                if (stack[top]) {
                    valid = false;
                    goto end;
                }
            }
        }

        stack[top] = false;

        p--;
    }

end:
    free(stack);
    return valid;
}


int main(int argc, char *argv[])
{
    char *line = NULL;
    size_t len = 0;
    ssize_t read;
    
    while((read = getline(&line, &len, stdin)) != -1) {
        char *p = line;
        int max = 0;
        /* check the max one */
        while(*p) {
            if (*p - '0' > max) {
                max = *p - '0';
            }
            p++;
        }
        *(p-1) = '\0'; /* remove trailing newline */
        printf("%s is %s\n", line, check(max, line) ? "Valid" : "Invalid");
    }

    free(line);
    return 0;
}