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

#define TAM 100000000

#define xDEBUG
#define xDEBUG_PRINTF

#define K_S_DEGUB

#ifdef DEBUG
    #ifdef DEBUG_PRINTF
        #define PRINT(A,...) printf(A,##__VA_ARGS__);
    #else
        #define PRINT(A,...) fprintf(saida,A,##__VA_ARGS__);
    #endif
#else
    #define PRINT(A,...) ;
#endif

char* remove_parenteses(char* vi) {
    char* final_expr = 0;
    int i;
    if (vi[0] != '(') {
        while(*(++vi) != '\0');
        return --vi;
    }
    int total = 0;
    while (vi[total] == '(') total++;
    int pos = 0, parent = 0;
    for (i = total; vi[i]; i++) {
        if (vi[i] == '(') {
            parent++;
            vi[pos++] = vi[i];
        }
        else if (vi[i] == ')') {
            if (parent>0) {
                parent--;
                vi[pos++] = vi[i];
            }
            else {
                total--;
            }
        }
        else {
            vi[pos++] = vi[i];
        }
    }
    vi[pos] = 0;
    if(!final_expr)
        final_expr = &vi[pos-1];

    return final_expr;
}

/*
 * Função que busca o início da expressão, ignorando os parênteses à esquerda da string.
 * Não remove os parênteses de fato. Retorna o endereço de interesse.
 *
 * O número de parênteses abrindo pode ser dado por remove_parenteses(str) - str
 */
char* remove_parenteses_abrindo(char* str) {
    for(;;++str)
        if(*str != '(')
            return str;
}

/*
 * Retorna o endereço do último parêntese baseado na quantidade de parênteses dada pelo arguemnto npar
 */
char* remove_parenteses_fechando(char* str, unsigned int npar, unsigned int* npar_ini) {
    if(npar == 0) {
        while(*(++str) != '\0');
        return --str;
    }


    for(;;++str)
        switch(*str) {
            case '(':
                ++npar;
                break;
            case ')':
                if(!(--npar))
                    return str;
                break;
            case '\0':
                return str;
                break;
            default:
                ++(*npar_ini);
                break;
        }

}

/*
 * Função que busca o próximo termo válido. Retorna o endereço final, que fica
 * no parêntese que fecha o termo, caso exista.
 * A entrada deve ser o primeiro endereço APÓS o operador.
 *
 * Esta função verifica também se existe algum parêntese fechando logo após o operador.
 * Se houver, deve-se diminuir a quantidade esperada de parênteses fechando no final da expressão.
 */
char* obtem_termo(char* str) {
    unsigned int parentese = 0;

    while(*(str++) == ')');
    --str;

    /* Colocando fora do laço ganha uma operação a menos por iteração */
    if(*str != '(' && *str != ')') return str;

    for(;;++str)
        switch(*str) {
            case '(':
                ++parentese;
                break;
            case ')':
                if(!(--parentese))
                    return str;
                break;
            default:
                break;
        }
}

char str[TAM] = "S(S(S(KS)(S(KK)(SKK)))(K(S(SKK)(SKK))))(S(S(KS)(S(KK)(SKK)))(K(S(SKK)(SKK))))((S(S(S(KS)(S(KK)(SKK)))(K(S(SKK)(SKK))))(S(S(KS)(S(KK)(SKK)))(K(S(SKK)(SKK))))((S(S(S(KS)(S(KK)(SKK)))(K(S(SKK)(SKK))))(S(S(KS)(S(KK)(SKK)))(K(S(SKK)(SKK))))((S(S(S(KS)(S(KK)(SKK)))(K(S(SKK)(SKK))))(S(S(KS)(S(KK)(SKK)))(K(S(SKK)(SKK))))((S(S(S(KS)(S(KK)(SKK)))(K(S(SKK)(SKK))))(S(S(KS)(S(KK)(SKK)))(K(S(SKK)(SKK))))((S(S(S(KS)(S(KK)(SKK)))(K(S(SKK)(SKK))))(S(S(KS)(S(KK)(SKK)))(K(S(SKK)(SKK))))((S(S(S(KS)(S(KK)(SKK)))(K(S(SKK)(SKK))))(S(S(KS)(S(KK)(SKK)))(K(S(SKK)(SKK))))((S(S(S(KS)(S(KK)(SKK)))(K(S(SKK)(SKK))))(S(S(KS)(S(KK)(SKK)))(K(S(SKK)(SKK))))((S(S(S(KS)(S(KK)(SKK)))(K(S(SKK)(SKK))))(S(S(KS)(S(KK)(SKK)))(K(S(SKK)(SKK))))((S(S(S(KS)(S(KK)(SKK)))(K(S(SKK)(SKK))))(S(S(KS)(S(KK)(SKK)))(K(S(SKK)(SKK))))(KK))K))K))K))K))K))K))K))K))K)";
char buf[TAM];
int main() {
    FILE *saida;
    saida = fopen("out.txt", "w");

    char* r = str;
    char* w = buf;

    char* inicio_expr;
    char* final_expr;
    char* a; size_t tam_a;
    char* b; size_t tam_b;
    char* c; size_t tam_c;
    char* d; size_t tam_d;

    #ifdef K_S_DEGUB
        unsigned int K_reducao = 0;
        unsigned int S_reducao = 0;
    #endif

    do {
        memset (w,'\0',TAM);

        final_expr = remove_parenteses(r);

        PRINT("str: %s\n",r);
        switch(*(inicio_expr = r)) {
            case 'K':
                #ifdef K_S_DEGUB
                    ++K_reducao;
                #endif

                a = obtem_termo(inicio_expr+1);

                b = obtem_termo(a+1);

                c = obtem_termo(b+1);

                PRINT("i: %s\na: %s\nb: %s\nc: %s\nf: %s\n", inicio_expr, a, b, c, final_expr);

                tam_a = a-inicio_expr;
                tam_b = b-a;

                memcpy(
                        memcpy(
                                w,
                                inicio_expr + 1,
                                tam_a
                        ) + tam_a,
                        b + 1,
                        (final_expr) - b
                );


                PRINT("--> %s\n", w);

                break;
            case 'S':
                #ifdef K_S_DEGUB
                    ++S_reducao;
                #endif

                a = obtem_termo(inicio_expr+1);

                b = obtem_termo(a+1);

                c = obtem_termo(b+1);

                d = obtem_termo(c+1);

                PRINT("i: %s\na: %s\nb: %s\nc: %s\nd: %s\nf: %s\n", inicio_expr, a, b, c, d, final_expr);

                tam_a = a-inicio_expr;
                tam_b = b-a;
                tam_c = c-b;

                w[0] = '(';
                memcpy(
                        memcpy(
                                w+1,
                                inicio_expr + 1,
                                tam_a
                        ) + tam_a,
                        b + 1,
                        c - b
                );
                w[1 + tam_a + tam_c]        = ')';
                w[1 + tam_a + tam_c + 1]    = '(';

                memcpy(
                        memcpy(
                                w+1 + (1 + tam_a + tam_c + 1),
                                a + 1,
                                b - a
                        ) + tam_b,
                        b + 1,
                        c - b
                    );
                w[(1 + tam_a + tam_c + 1) + (1 + tam_b + tam_c)]        = ')';


                memcpy(
                    w+1 + ((1 + tam_a + tam_c + 1) + (1 + tam_b + tam_c)),
                    c + 1,
                    strlen(c + 1)
                );


                PRINT("--> %s\n", w);

                break;
            default:
                break;
        }
        /* swap */
        inicio_expr = w;
        w = r;
        r = inicio_expr;
    } while(r[1] != '\0');

    fprintf(saida, "--> %s\n", w);

    fprintf(saida, "--> %s\n", r);

    #ifdef K_S_DEGUB
        fprintf(saida, "K reducoes: %d\nS reducoes: %d\n", K_reducao, S_reducao);
    #endif

    return 0;
}