programming puzzle: matching parens.

c_output.txt

$ gcc -O3 -std=c99 -Wall parens.c

$ ./a.out parens-tests/100k.txt 
answer: 1
elapsed time: 13.773000ms

$ ./a.out parens-tests/1million.txt 
answer: 1
elapsed time: 125.703000ms

$ ./a.out parens-tests/10million.txt 
answer: 1
elapsed time: 1257.168000ms

parens.c

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

char* openers = "([{";
char* closers = ")]}";

struct _chstack_t {
    char ch;
    struct _chstack_t* next;
};
typedef struct _chstack_t chstack_t;

void stack_free(chstack_t* stack) {
    chstack_t* next;
    while (stack != NULL) {
        next = stack->next;
        free(stack);
        stack = next;
    }
}

void push(chstack_t** stack, char ch) {
    chstack_t* new_head = (chstack_t*)malloc(sizeof(chstack_t));
    new_head->ch = ch;
    new_head->next = *stack;
    *stack = new_head;
}

bool pop(chstack_t** stack, char* ch) {
    assert(stack != NULL);
    if (*stack == NULL) {
        return false;
    }
    chstack_t* old_head = *stack;
    *ch = old_head->ch;
    (*stack) = (*stack)->next;
    if (old_head != NULL) {
        free(old_head);
    }
    return true;
}

char opposite(char ch) {
    if (ch == ')') { return '('; }
    if (ch == ']') { return '['; }
    if (ch == '}') { return '{'; }
    assert(false);
}

bool bal(char* s) {
    bool answer;
    chstack_t* stack = NULL;

    size_t len = strlen(s);
    for (size_t i = 0; i < len; i++) {
        char ch = s[i];
        if (strchr(openers, ch)) {
            // printf("pushing opener: %c\n", ch);
            push(&stack, ch);
        }
        else if (strchr(closers, ch)) {
            // printf("closer");
            char stack_ch;
            bool did_pop = pop(&stack, &stack_ch);
            if (!did_pop) {
                // printf(", couldn't pop\n");
                answer = false;
                goto cleanup;
            } else if (opposite(ch) != stack_ch) {
                // printf(", didn't match stack: opp: %c, != %c\n", opposite(ch), stack_ch);
                answer = false;
                goto cleanup;
            } else {
                // printf("\n");
            }
        }
    }

    answer = stack == NULL;

cleanup:
    stack_free(stack);
    stack = NULL;
    return answer;
}

// Thanks to https://stackoverflow.com/a/174552/7543271
char* read(char* fname) {
    char* buffer = 0;
    long length;
    // printf("opening file: %s\n", fname);
    FILE* f = fopen(fname, "rb");

    if (f) {
        fseek(f, 0, SEEK_END);
        length = ftell(f);
        // printf("file length: %li\n", length);
        fseek(f, 0, SEEK_SET);
        buffer = malloc(length);
        if (buffer) {
            fread(buffer, 1, length, f);
        }
        fclose(f);
    }
    return buffer;
}

#include <sys/time.h> // for gettimeofday()

void bench(char* fname) {
    // printf("reading file...\n");
    char* s = read(fname);

    // printf("benchmarking...\n");
    struct timeval then;
    struct timeval now;
    double elapsed;

    gettimeofday(&then, NULL);
    bool answer = bal(s);
    gettimeofday(&now, NULL);
    printf("answer: %i\n", answer);
    // thanks to https://stackoverflow.com/a/2150334/7543271
    elapsed = (now.tv_sec - then.tv_sec) + (now.tv_usec - then.tv_usec) / 1000000.0;
    printf("elapsed time: %fms\n", elapsed * 1000.0);
    assert(answer);
}

int main(int argc, char** argv) {
    // printf("%i\n", bal("()"));
    // printf("%i\n", bal("(())"));
    // printf("%i\n", bal("("));
    bench(argv[1]);
    return EXIT_SUCCESS;
}

parens.py

#!/usr/bin/env python

import sys
import time

def opposite(ch):
    if ch == ')': return '('
    if ch == ']': return '['
    if ch == '}': return '{'

openers = ['(', '[', '{']
closers = [')', ']', '}']

def bal(s):
    stack = []
    for ch in s:
        if ch in openers:
            stack.append(ch)
        elif ch in closers:
            try:
                if opposite(ch) != stack.pop():
                    return False
            except:
                return False
    return len(stack) == 0

def test():
    with open('correct.txt') as f:
        for s in f.readlines():
            assert bal(s)
    with open('incorrect.txt') as f:
        for s in f.readlines():
            assert not bal(s)

def bench(fname):
    with open(fname) as f:
        s = f.read()
        then = time.time()
        b = bal(s)
        now = time.time()
        print b
        elapsed = now - then
        print "elapsed: %fms" % (elapsed * 1000)

if __name__ == "__main__":
    if len(sys.argv) >= 3 and sys.argv[1] == "-b":
        fname = sys.argv[2]
        bench(fname)
    else:
        test()

py_output.txt

$ ./parens.py -b parens-tests/100k.txt 
True
elapsed: 53.959846ms

$ ./parens.py -b parens-tests/1million.txt 
True
elapsed: 525.941133ms

$ ./parens.py -b parens-tests/10million.txt 
True
elapsed: 5248.156071ms