excel formula compiler 130% done

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

#define MAX_OPERANDS 100
#define MAX_DICT 1024
#define FILE_BUF 1024

/* dict.dat
add2    ($0+$1)
add3    ($0+$1+$2)
add4    ($0+$1+$2+$3)
add5    ($0+$1+$2+$3+$4)
add6    ($0+$1+$2+$3+$4+$5)
add15   ($0+$1+$2+$3+$4+$5+$6+$7+$8+$9+$10+$11+$12+$13+$14)
mul2    ($0*$1)
mul3    ($0*$1*$2)
mul4    ($0*$1*$2*$3)
mul5    ($0*$1*$2*$3*$4)
mul6    ($0*$1*$2*$3*$4*$5)
div2    ($0/$1)
sub2    ($0-$1)
sub1    (-$0)
ifthen  И($0)*($1)
and2    И($0;$1)*($2)
# 1d линейная интерполяция по двум точкам f(x x1 x2 y1 y2)
interp1d    И($0>=$1;$0<$2)*(($0-$1)/($2-$1)*($4-$3)+$3)
# 2d линейная интерполяция по четырём точкам f(x y x1 x2 y1 y2 z11 z12 z21 z22)
interp2d    И($0>=$2;$0<$3;$1>=$4;$1<$5)*((($1-$4)/($5-$4)*($9-$7-$8+$6)+$7-$6)*($0-$2)/($3-$2)+($1-$4)/($5-$4)*($8-$6)+$6)

 */

/* try me

add3(ifthen(B1<7;add6(interp1d(A1;0,45;0,55;4;4);interp1d(A1;0,55;0,65;4;3,5);interp1d(A1;0,65;0,75;3,5;3);interp1d(A1;0,75;0,85;3;2);interp1d(A1;0,85;0,95;0;0);interp1d(A1;0,95;1,05;0;0)));and2(B1>=7;B1<17;add6(interp1d(A1;0,45;0,55;5;5);interp1d(A1;0,55;0,65;5;4,5);interp1d(A1;0,65;0,75;4,5;4);interp1d(A1;0,75;0,85;4;3);interp1d(A1;0,85;0,95;3;2,5);interp1d(A1;0,95;1,05;2,5;2)));ifthen(B1>=17;add6(interp1d(A1;0,45;0,55;0;0);interp1d(A1;0,55;0,65;0;0);interp1d(A1;0,65;0,75;6;6);interp1d(A1;0,75;0,85;6;5,5);interp1d(A1;0,85;0,95;5,5;5);interp1d(A1;0,95;1,05;5;4,5))))

*/

struct excel_exp;

char* excel_alloc_string(size_t len);

struct excel_rewrite {
    char* name[MAX_DICT];
    char* val[MAX_DICT];
    int num;
} excel_rewrite_dict;

/** Читает список функций из файла dict.dat, заполняет ими excel_rewrite_dict.
 *
 */
void excel_init_dict() {
    FILE* f = fopen("dict.dat","r");
    memset(&excel_rewrite_dict,0,sizeof(struct excel_rewrite));

    char buf[FILE_BUF];
    if ( f==0 )
    {
        fprintf(stderr,"error opening file dict.dat\n");
        return ;
    }
    int n = 0;
    while (!feof(f))
    {
        fgets(buf,FILE_BUF,f);
        char* p = strchr(buf,'\t');

        if (buf[0] == '#')
            continue ;

        if (p) {
            int l1 = strlen(buf);
            int l2 = strlen(p);

            char* name = excel_alloc_string(l1-l2);
            strncat(name,buf,l1-l2);
            char* val = excel_alloc_string(l2-1);
            strncat(val,p+1,l2-2);

            excel_rewrite_dict.name[n] = name;
            excel_rewrite_dict.val[n] = val;
            ++n;
        }
    }
    excel_rewrite_dict.num = n-1;
}

/** Освобождает память, очищая список определенных функций
 *
 */
void excel_uninit_dict() {
    int i;
    for (i=0;i<excel_rewrite_dict.num;i++)
    {
        free(excel_rewrite_dict.name[i]);
        free(excel_rewrite_dict.val[i]);
    }
}

/** Выражение: имя, операнды, значение.
 *  Операнды могут быть как строками op, так и вложеными выражениями ope
 */
struct excel_exp {
    char* name;
    char* op[MAX_OPERANDS];
    struct excel_exp* ope[MAX_OPERANDS];
    int num;
    char* val;
};

struct excel_exp* excel_parse(char* exp);

/** Выделяет память под выражение
 *
 */
struct excel_exp* excel_alloc_exp() {
    struct excel_exp* exp;
    exp = malloc(sizeof(struct excel_exp));
    memset(exp,0,sizeof(struct excel_exp));
    return exp;
}

/** Выделяет память под строку
 *
 */
char* excel_alloc_string(size_t len) {
    char* s = (char*) malloc(len+1);
    memset(s,0,len+1);
    return s;
}

/** Определяет является ли строка выражением.
 *  Другими словами, содержит ли строка ';'
 */
int excel_isexp(char* exp) {
    if (strchr(exp,';')!=0) {
        //printf("%s is exp",exp);
        return 1;
    }
    //printf("%s is not exp",exp);
    return 0;
}

/** Определяет есть ли в выражении нераспарсеные вложеные выражения
 *
 */
int excel_isleaf(struct excel_exp* exp) {
    int i=-1;
    while (++i<exp->num) {
        if (exp->ope[i]) return 0;
    }
    return 1;
}

/** Очищает память, выделенную под операнды и имя функции
 *
 */
void excel_free_op(struct excel_exp* exp) {
    int j;
    free(exp->name);
    exp->name = 0;
    for (j=0;j<exp->num;j++)
    {
        free(exp->op[j]);
        free(exp->ope[j]);
        exp->op[j] = 0;
        exp->ope[j] = 0;
    }
    exp->num = 0;
}

/** Подсчитывает число использования операндов в шаблоне
 *  Операнды в шаблоне обозначаются как $0, $1 ... $9
 *  @todo escaping \$
 */
int excel_count_vars(char* val) {
    int n = 0;
    char* p = val;
    while (p) {
        p = strchr(p+1,'$');
        if (p) n++;
    }
    return n;
}

/** Определяет длинну самого длинного операнда
 *
 */
int excel_max_op_length(struct excel_exp* exp) {
    int maxl = 0;
    int li = 0;
    int j;
    for (j=0;j<exp->num;j++)
    {
        li = strlen(exp->op[j]);
        if (li>maxl) maxl = li;
    }
    return maxl;
}

/** Очищает память выделенную под выражение
 *
 */
void excel_free_exp(struct excel_exp* exp) {
    excel_free_op(exp);
    free(exp->val);
    free(exp); // не догоняю почему всё падает
}

/** Переписывает выражение, используя словарь excel_rewrite_dict
 *  Находит в словаре шаблон по имени функции и подставляет в него операнды.
 *  Если не найдет поставит undefined
 */
void excel_rewrite(struct excel_exp* exp) {
    int i,j;
    for (i=0;i<excel_rewrite_dict.num;i++)
    {
        if (strcmp(exp->name,excel_rewrite_dict.name[i]) == 0)
        {
            // на результирующую строку будет достаточно n символов, где
            // n = длинна шаблона + число использования операндов в шаблоне * длинна самого длинного операнда
            int li = excel_max_op_length(exp);
            int n = excel_count_vars(excel_rewrite_dict.val[i]);
            int l = li * n + strlen(excel_rewrite_dict.val[i]);
            char* val = excel_alloc_string(l);

            char* p = excel_rewrite_dict.val[i];
            while(*p) {
                if (*p == '$') {
                    ++p;

                    int i = 0;
                    char d1,d2;
                    d1 = *p;
                    d2 = *(p+1);

                    if (d2>='0' && d2 <='9') {
                        i = (d1 - '0')*10 + (d2 - '0');
                        ++p;
                    } else {
                        i = (d1 - '0');
                    }

                    if (i>=0 && i<MAX_OPERANDS && exp->op[i])
                        strcat(val,exp->op[i]);
                } else {
                    strncat(val,p,1);
                }
                ++p;
            }
            excel_free_op(exp);
            exp->val = val;
            return;
        }
    }
    fprintf(stderr,"%s undefined\n",exp->name);
    excel_free_op(exp);
    char* undef = excel_alloc_string(10);
    strcat(undef,"undefined");
    exp->val = undef;
}

/** Поднимается по дереву выражений, переписывая функции по словарю в бездетных
 *  (крайних) нодах, разбирая дерево.
 *  Если всё дерево разобрано, возвращает 1
 */
int excel_collapse(struct excel_exp* exp) {
    int i;

    if (exp->val)
        return 1;
    if (excel_isleaf(exp))
        excel_rewrite(exp);

    for (i=0;i<exp->num;i++)
    {
        if (exp->ope[i]) {
            excel_collapse(exp->ope[i]);
            if (exp->ope[i]->val) {

                free(exp->op[i]);
                exp->op[i] = exp->ope[i]->val;

                excel_free_op(exp->ope[i]);
                free(exp->ope[i]);
                exp->ope[i] = 0;
            }
        }
    }
    return 0;
}

struct excel_exp* excel_build_tree(char* exp);

/** Парсит строку в дерево выражений
 */
struct excel_exp* excel_build_tree(char* exp) {

    struct excel_exp* root = excel_alloc_exp();

    /* идем по строке отмечая ; не вложеные в скобки, также отмечаем первую
     * открывающую и последнюю закрывающую скобку, чтобы выделить называние
     * функции и операнды
     * название_функции(операнд;операнд;вложеная_функция(операнд;операнд);операнд)
     * semicolon:     [0]     [1]     [2]                               [3]     [4]
     * j==5; exp->num = j-1
     */
    size_t l = strlen(exp);
    int semicolon[MAX_OPERANDS+1];
    int parenthesis = 0;
    int i = -1;
    int j = 0;
    while (++i<l) {
        switch (exp[i]) {
            case '(' : if (j==0) {semicolon[j++] = i;} parenthesis++; break;
            case ')' : parenthesis--; if (parenthesis == 0) semicolon[j++] = i; break;
            case ';' : if (parenthesis == 1) semicolon[j++] = i; break;
        }
        if (j>MAX_OPERANDS+1) {
            fprintf(stderr,"MAX_OPERANDS exceeded in %s\n",exp);
            return 0;
        }
    }
    if (parenthesis > 0)
        fprintf(stderr,"unmatched parenthesis, need %i ) more\n",parenthesis);
    if (parenthesis < 0)
        fprintf(stderr,"unmatched parenthesis, need %i ( more\n",-parenthesis);
    --j;

    size_t li = semicolon[0];
    char* name = excel_alloc_string(li);
    strncpy(name,exp,li);
    root->name = name;
    root->num = j;

    for (i=0;i<j;i++)
    {
        li = semicolon[i+1] - semicolon[i] - 1;

        if (li>0)
        {
            char* opi = excel_alloc_string(li);
            strncpy(opi, exp + semicolon[i]+1,li);

            if (excel_isexp(opi))
                root->ope[i] = excel_build_tree(opi);
            root->op[i] = opi;
        } else {
            root->num = root->num - 1;
        }
    }

    return root;
}

/** Переписывает фунции двигаясь
 *  от ветвей к корню. В exp->val оказывается результат
 */
char* excel_collapse_tree(struct excel_exp* exp) {
    // трясём дерево пока не упадёт
    int r = 0;
    while (r != 1)
        r = excel_collapse(exp);
    return exp->val;
}

int main(int argc, char** argv) {
    char* exp_string = 0;
    excel_init_dict();
    if (excel_rewrite_dict.num < 1) {
        fprintf(stderr,"dict.dat has no records, please create dict.dat\n");
        fprintf(stderr,"dict.dat format: each line has the name of the function\n");
        fprintf(stderr,"and value to replace it with, separated with tab\n");
        fprintf(stderr,"example:\nadd2  ($0+$1)\nmul2   ($0*$1)\n");
        return 0;
    }

    if (argc>1 && strcmp(argv[1],"--help")!=0 && strcmp(argv[1],"-h")!=0 && strcmp(argv[1],"/?")!=0)
    {
        exp_string = argv[1];
    }
    else
    {
        printf("usage: compiler.exe \"formula\"\nexample: compiler.exe \"add2(mul2(A1;A2);2)\"\n");
        return 0;
    }

    struct excel_exp* exp = excel_build_tree(exp_string);
    char* val = excel_collapse_tree(exp);
    printf("=%s",val);
    excel_free_exp(exp);

    excel_uninit_dict();
    return 0;
}