excel_formula_compiler.c

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

#define MAX_OPERANDS 10
#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)
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)
interp  И($0>=$1;$0<$2)*(($0-$1)/($2-$1)*($4-$3)+$3)

 */

/*char* test = "add3(ifthen(B1<7;add6(interp(A1;0,45;0,55;4;4);interp(A1;0,55;0,65;4;3,5);interp(A1;0,65;0,75;3,5;3);interp(A1;0,75;0,85;3;2);interp(A1;0,85;0,95;0;0);interp(A1;0,95;1,05;0;0)));and2(B1>=7;B1<17;add6(interp(A1;0,45;0,55;5;5);interp(A1;0,55;0,65;5;4,5);interp(A1;0,65;0,75;4,5;4);interp(A1;0,75;0,85;4;3);interp(A1;0,85;0,95;3;2,5);interp(A1;0,95;1,05;2,5;2)));ifthen(B1>=17;add6(interp(A1;0,45;0,55;0;0);interp(A1;0,55;0,65;0;0);interp(A1;0,65;0,75;6;6);interp(A1;0,75;0,85;6;5,5);interp(A1;0,85;0,95;5,5;5);interp(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');
        int l1 = strlen(buf);
        int l2 = strlen(p);

        if (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));
}

/** Выделяет память под строку
 *
 */
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;
                    n = (*p) - '0';
                    if (n>=0 && n<MAX_OPERANDS && exp->op[n])
                        strcat(val,exp->op[n]);
                } 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);
    exp->val = "undefined";
}

/** Поднимается по дереву выражений, переписывая функции по словарю в бездетных
 *  (крайних) нодах, разбирая дерево.
 *  Если всё дерево разобрано, возвращает 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;
}

/** Парсит строку в дерево выражений, потом переписывает фунции двигаясь
 *  от ветвей к корню. В exp->val оказывается результат
 */
struct excel_exp* excel_parse(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_parse(opi);
            root->op[i] = opi;
        } else {
            root->num = root->num - 1;
        }
    }

    // трясём дерево пока не упадёт
    int r = 0;
    while (r != 1) {
        r = excel_collapse(root);
    }

    return root;
}

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_parse(exp_string);
    printf("=%s",exp->val);
    excel_free_exp(exp);

    excel_uninit_dict();
    return 0;
}