20140529 :: Strings

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

const int kMaxStringLength = 5000;
const int kMaxBracketLength = 10;

void output(FILE * out, char * msg) {
    fprintf(out, "%s\n", msg);
}

char * inputStr(FILE * in, int buffer) {
    char * ret = (char *)malloc(buffer * sizeof(char));
    fgets(ret, buffer, in);
    if (ret[strlen(ret) - 1] == '\n') {
        ret[strlen(ret) - 1] = '\0';
    }
    return ret;
}

void process(char ** str, char * op, char * cl) {
    int ls = strlen(*str) + 1;
    int size = ls * sizeof(int);

    int * opPos = (int *)malloc(size);
    char * strOffset = *str;
    int opPosCnt = 0;
    while ((strOffset = strstr(strOffset, op)) != NULL) {
        opPos[opPosCnt++] = strOffset - *str + strlen(op) - 1;
        ++strOffset;
    }

    int * clPos = (int *)malloc(size);
    strOffset = *str;
    int clPosCnt = 0;
    while ((strOffset = strstr(strOffset, cl)) != NULL) {
        clPos[clPosCnt++] = strOffset - *str;
        ++strOffset;
    }

    int * badPositions = (int *)malloc(size);
    memset(badPositions, 0, size);
    int * stack = (int *)malloc(size);
    int stackTop = 0;
    for (int i = 0, j = 0; i < opPosCnt || j < clPosCnt; ) {
        if (i < opPosCnt && opPos[i] >= clPos[j] || i == opPosCnt) {
            if (stackTop == 0) {
                ++j;
            } else {
                badPositions[stack[--stackTop] + 1 - strlen(op)] = 1;
                badPositions[clPos[j++] + strlen(cl)] = -1;
                while (i < opPosCnt && opPos[i] < clPos[j]) {
                    ++i;
                }
            }
        } else {
            stack[stackTop++] = opPos[i++];
        }
    }
    int curBalance = 0;
    int curPos = 0;
    for (int i = 0; i < ls; ++i) {
        curBalance += badPositions[i];
        if (curBalance == 0) {
            (*str)[curPos++] = (*str)[i];
        }
    }
    (*str)[curPos] = '\0';

    free(stack);
    free(badPositions);
    free(opPos);
    free(clPos);
}

int main() {
    FILE * in = fopen("input.txt", "r");
    FILE * out = fopen("output.txt", "w");

    output(out, "Enter string:");
    char * str = inputStr(in, kMaxStringLength);
    output(out, "Enter opening bracket:");
    char * op = inputStr(in, kMaxBracketLength);
    output(out, "Enter closing bracket:");
    char * cl = inputStr(in, kMaxBracketLength);
    process(&str, op, cl);
    output(out, str);

    free(op);
    free(cl);
    free(str);
    fclose(in);
    fclose(out);
    return 0;
}