Programming Challenges

C: gcc -O2 hard.c

This is very poorly written, but does seem to work.

The stack keeps track of the start of a match, and the character that would complete the match. In cases where a match just ended, the start is preserved (because two adjacent matches are effectively one), but the required matching character is changed to that of the new opening match.

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

int main(int argc, char **argv)
{
	char map[256] = { 0 };
	struct match {
		char const *start;
		char requirement;
	};
	char const *match_start;
	ptrdiff_t length = 0;
	char const *p;
	struct match *stack, *top;
	char opener;

	if (argc != 2) {
		fputs("Improper invocation\n", stderr);
		exit(EXIT_FAILURE);
	}

	/* Initialise lookup table */
	map[')'] = '(';
	map[']'] = '[';
	map['}'] = '{';

	if (!(stack = calloc(sizeof(*stack), strlen(argv[1]) + 1))) {
		fputs("Allocation failure\n", stderr);
		exit(EXIT_FAILURE);
	}
	/* Note: stack[0].requirement must be 0. This is satisfied by calloc. */
	top = stack;

	match_start = argv[1];
	for (p = argv[1]; *p; p++) {
		/* Are we a closing brace? */
		if ((opener = map[(size_t)*p])) { /* Yes */
			if (top->requirement == opener) {
				if (p - top->start >= length) {
					length = p - top->start + 1;
					match_start = top->start;
				}
				top[1].start = 0;
				top--;
			} else {
				top[1].start = 0;
				/* Set start to nullptr to invalidate the matches */
				while (top > stack) {
					top--->start = 0;
				}
			}
		} else { /* No */
			(++top)->requirement = *p;
			/* If we are right outside another match, we can use their pointer instead */
			if (!top->start) {
				top->start = p;
			}
		}
	}

	printf("%.*s\n", (int)length, match_start);

	free(stack);
}