在C中解析数学表达

Question

我正在编写一个简单的计算器，该计算器接受命令行中的参数并评估字符串。 故意，它应该接受数学表达并评估它，但在运行它时会引发一些错误。但是，它被成功地编译了。

它引发了以下错误： -

分割故障

free（）：在TCACHE 2中检测到双免费检测 中止

realloc（）：下一个尺寸无效 中止

是我的calc.c

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#include<math.h>
#include"replace.h"


#define EXPL 200 //expression lenght
#define MAXLEN 512
#define HAFLEN 256

void DisplayHelp(void);
int validate(char*);
int issign(char);
char* evaluate(char*);
long double calculate(char*);
long double getNext(char*);
long double getPrev(char*, char*);
int calcValidate(char*);
void operate(char*, char);
int issign(char);
long double strtonum(char*);


void DisplayHelp(){
    char str[] = "calc <expression>\n"\
    "expression: it is the mathematical expression that is to be calculated or evaluated.\n"\
    "You can also use just 'calc' without any argument to start a calculator program.\n";
    printf("%s\n",str);
}

int issign(char s)
{
    char signs[8] = "-+/*^";
    if(strchr(signs, s))
        return 1;
    return 0;
}
int validate(char *src)
{
    char *init = src;
    //check if all the characters are acceptable
    while (*src){
        if( 
            isdigit(*src)
            || *src == '(' || *src == ')' 
        || *src == '.' || *src == '+' 
        || *src == '-' || *src == '^'
        || *src == '/' || *src == '*' 
        )
            src++;
            else{
                puts(init);
                printf("Expression Contains Illegal Character at position %d.\n", (int)(src - init) + 1);
                return 0;
            }
    }
    
    //check if there is brace after operator
    src = init;
    if(strstr(src, "-)") || strstr(src, "+)") 
        || strstr(src, "/)") || strstr(src, "*)")
        || strstr(src, "^)")){
            printf("Expected a number after after operator. Got brace ')'\n");
            return 0;
        }
        
        //check missing brackets
        int hasBrace = 0;
    if(strchr(src, '('))
        hasBrace = 1;
    
    src = init;
    int brace = 0;
    while(*src){
        if(*src == '(')
            ++brace;
        else if(*src == ')')
            brace -= 1;
        ++src;
    }
    if(brace){
        printf("%d Missing braces\n", brace);
        return 0;
    }
    
    //check for missing operator after or before  braces and add multiply operator in between
    if(hasBrace){
        //first count how many * should be inserted and store the index
        src = init;
        int insCount = 0;
        int index[(int)strlen(src)];
        // printf("%ld size of array, %ld\n", sizeof(index)/sizeof(int), strlen(init));
        while(*src){
            if(*src == '(' || *src == ')'){
                if(*src == '('){
                    if(src != init) --src;
                   if(isdigit(*src)){
                       index[insCount] = (int)(src  - init) + 1; // index of (
                           ++insCount;
                   }
                   ++src;
                }
                else if(*src == ')'){
                           ++src;
                           if(isdigit(*src) || *src == '('){
                               index[insCount] = (int)(src - init);
                               ++insCount;
                           }
                           --src;
                }
            }
            ++src;
        }
        //now insert * in the indexed position
        src = init;
        char  *tmp = (char*)malloc(((int)strlen(src) + insCount + 1) * (int)sizeof(char)); //+1 for \0
        if(tmp == NULL)
            exit(-1);
        strcpy(tmp, src);
        //store how many * added as it will change the other stored index in the array
        int added = 0;
        for(int i = 0; i < insCount; ++i){
            char *ret = insert(tmp, "*", index[i] + added);
            strcpy(tmp, ret);
            ++added;
            free(ret); 
        }
        src = realloc(src, strlen(tmp)  + 1);
        strcpy(src, tmp);
        free(tmp);
    }
    
    //check for empty braces
    src = init;
    if(hasBrace){
        while(*src){
            if(*src == '('){
                ++src;
                if(*src == ')'){
                printf("Empty braces.\n");
                return 0;
                }
                --src;
            }
            src++;
        }
    }
    
    //check if expression contains operators in invalid place
    if(!calcValidate(init)){
        puts("Got unexpected operator(s) at unexpected place");
        return 0;
    }
    
    
    return 1;
}

char* evaluate(char *exp)
{
    //since we will insert every result of evaluation in the exp, it may contain exp and resutl or brac exp like 3^4^3 so very long
    exp = realloc(exp, MAXLEN);
    if(!exp)
        exit(-1);
    char *init = exp;
    long expl = strlen(exp);
    
    //count total open brackets
    int brace = 0;
    while(*exp){
        if(*exp == '(')
            ++brace;
        ++exp;
    }
    exp = init;
    int isWholeInsideBrace = 0;
    if(*exp == '(')
        isWholeInsideBrace = 1;
    
    if(brace){
        for(int i = brace; i > 0; --i){
            int bracth = 0; //nth brace e.g. 4th brace
            char bracexp[MAXLEN] = "";
            char curAns[MAXLEN] = ""; //store current ans, later replace bracexp in exp with it
            char *bracclos = "";
            while(*exp){
                if(*exp == '('){
                    ++bracth;
                    if(bracth != i){
                        ++exp;
                        continue;
                    }
                    bracclos = strchr(exp, ')');
                strncpy(bracexp, exp, bracclos - exp + 1); //copy from '(' to ')'
    snprintf(curAns, MAXLEN, "%.256Lg", calculate(bracexp));
    char *replExp = replace(init, bracexp, curAns, 1);
    strcpy(init, replExp);
    free(replExp);
    // exit(0);
    break;
    
                }
                ++exp;
            }
            exp = init;
        }
    } 
    if(!isWholeInsideBrace){
        snprintf(exp, MAXLEN, "%.256Lg", calculate(exp));
    }
    return exp;
}

long double calculate(char* expre)
{
    char tmp[MAXLEN] = "";
    long double ans = 0.0;
    char* ptr = tmp;
    
    //remove brace from if exist
    while(*expre){
        if(*expre != '(' && *expre != ')'){
            *ptr = *expre;
            ++ptr;
        }
        ++expre;
    }
    *ptr = '\0';
    ptr = tmp;
    
    if(strchr(tmp, '^'))
        operate(tmp, '^');
    
    if(strchr(tmp, '/'))
        operate(tmp, '/');
    
    if(strchr(tmp, '*'))
        operate(tmp, '*');
    
    // for + and - need to check if there is only one number, else infinite loop        
    if(strchr(tmp, '+') )
        operate(tmp, '+');
    
    if(strchr(tmp, '-') )
        operate(tmp, '-');
    
    //if the exp does not contain any signs means it if already calculated or it is single number
    return atof(tmp);
}

void operate(char *temp, char sign)
{
    long double num1 = 0;
    long double num2 = 0;
    char curExp[MAXLEN] = "";
    char curAns[MAXLEN] = "";
    char *replaced;
    char *oper;
    
    long double ans = 0;
    while((oper = strchr(temp,sign))){
        num1 = getPrev(temp, oper);
        num2 = getNext(oper);
        
        if(sign == '^')
            ans = pow(num1, num2);
        else if(sign == '/')
            ans = num1 / num2;
        else if(sign == '*')
            ans = num1 * num2;
        else if(sign == '+')
            ans = num1 + num2;
        else if(sign == '-')
            ans = num1 - num2;
        
        //if first letter is + or - , getPrev returns 0 so ignore it
        //check and specify the format
        char secfor[15] = "";
        char ansfor[10] = "";
        
        if(oper == temp && !isdigit(*oper))
            snprintf(curExp, MAXLEN,((int)num2 == num2)? "%c%.0Lf" : "%c%.4Lf", *oper, num2);
        else{
            int a,b;
            a = (int)num1;
            b = (int)num2;
            if(a == num1 && b ==  num2)
                strcpy(secfor, "%.0Lf%c%.0Lf");
            else if(a == num1)
                strcpy(secfor, "%.0Lf%c%.4Lf");
            else if(b == num2)
                strcpy(secfor, "%.4Lf%c%.0Lf");
            else
                strcpy(secfor, "%.4Lf%c%.4Lf");
            
            snprintf(curExp, MAXLEN, secfor, num1, *oper, num2);
        }
        
        snprintf(curAns, MAXLEN,((int)ans == ans)? "%.0Lf" : "%.4Lf", ans);
        replaced = replace(temp, curExp, curAns, 1);
        // printf("%s\n%s\t%s\n%s\n", temp, curExp, curAns, replaced);
        strcpy(temp, replaced);
        printf("new temp: %s\n\n", temp);
        
        free(replaced);
        //special cases:-
        //if first letter is + or - and there is only one number, so break the loop
        if(sign == '+' || sign == '-'){
            char *ptr = temp;
            if(sign == '+'){
                if(strrchr(temp, '+') == ptr && !strchr(temp, '-'))
                    break;
            }
            else if(sign == '-'){
                if(strrchr(temp, '-') == ptr)
                    break;
            }
        }    
    }
}

int calcValidate(char *val)
{
    char *point = val;
    char first = *point;
    //take pointer to end of string
    point = strchr(point, '\0');
    --point;
    char last = *point;
    point = val;
    
    if(!isdigit(first) && (first != '-' || first != '+'))
        return 0;
    else if(!isdigit(last) && last != '(' && last != ')')
        return 0;
    
    //check whether operators are doubled
    int doubled = 0;
    while(*point){
        if(isdigit(*point) || *point == '(' || *point == ')')
            doubled = 0;
        else if(issign(*point)){
            if(doubled)
                return 0;
            doubled = 1;
        }
        ++point;
    }
    return 1;
}

long double getNext(char* pos)
{
    char *tmp = pos;
    //pos is the position of operator, ignore it, and return numbers from it to next operator
    ++tmp;
    return strtonum(tmp);
}

long double getPrev(char* str, char* pos)
{
    char *tmp = str;
    char *tmpp = pos;
    //if + or - is at first, return 0
    if(tmpp == str)
        return 0;
    --tmpp;
    while(tmpp != str  && isdigit(*tmpp))
        --tmpp;
    //tmpp now is the position of operator , so get number between this operator to another operator i.e. pos
    if(tmpp != str)
        ++tmpp;
    return strtonum(tmpp);
}

long double strtonum(char* s)
{
    char *ptr = s;
    char sign = '\0';
    long double beforeDecimal = 0.0;
    float afterDecimal = 0.0;
    
    float a, c = 10;
    int exp = 1;
    if(*ptr == '+' || *ptr == '-'){
        sign = *ptr;
        ++ptr;
    }
    while(isdigit(*ptr)){
        a = *ptr - '0';
    beforeDecimal = beforeDecimal * c + a;
    ++ptr;
    }
    if(*ptr == '.'){
        ++ptr;
        while(isdigit(*ptr)){
            a = *ptr - '0';
    afterDecimal = afterDecimal + a/pow(c, exp);
    ++exp;
    ++ptr;
        }
    }
    beforeDecimal += afterDecimal;
    if(beforeDecimal){
        if(sign && sign == '-')
            beforeDecimal = -beforeDecimal;
        return beforeDecimal;
    }
    
    return 0;    
}

int main(int argc, char const *argv[])
{
    //parse and store the expression for calculation
    char *exp = (char*)malloc(sizeof(char) * (EXPL +1)); // 1 is for null terminator \0
    if(exp == NULL)
        exit(-1);
    
    int count = 1; //extra 1 will store \0
    int i = 1, j = 1;
    
    // check whether argument are supplied
    if(argc < 2)
        return 0;
    
    //calculate the total size of arguments
    while(j < argc){
        count += strlen(argv[j]);
        ++j;
    }
    char *temp = malloc(sizeof(char) * count);
    if(!temp) exit(-1);
       //copy all arguments to temp
       for(i = 1; i < argc; ++i)
           strcat(temp, argv[i]);
       //check if the expression contains whitespaces
       //first check if it contains multiline argument and make it single line
       //then remove whitespaces
       if(strstr(temp," ") || strstr(temp, "\n")){
           char *tmp = temp;
           char *init = temp;
           while(*temp != '\0'){
               //remove all the \n
               if(*temp != ' ' && *temp != '\n'){
                   *tmp = *temp;
                   ++tmp;
               }
               ++temp;
           }
           *tmp = '\0';
    temp = init;
       }
       // check if the expression is within the limit i.e EXPL
       if(count > EXPL){
           printf("Expression is too long;\nMax %d digits.\nGiven %d\n ", EXPL, count);
           return 1;
       }
       else
           strcpy(exp, temp);
       free(temp);
       
       if(!validate(exp)){
           free(exp);
           return 1;
       }
       //since the expression is ready to be evaluated, let's evaluate it to produce the result
       evaluate(exp);
       puts(exp);
       free(exp);
       return 0;
}

是替换。

#include"replace.h"

char *replace(char *str,char *substr,  char *seed, int recursive)
{
    char *firstPos = strstr(str, substr);
    if(!firstPos)
        return NULL;

    long size = 0;
    long  strS, substrS, seedS, occurance;
    strS = substrS = seedS = occurance = 0;
    //calculate length of substr, seed and str
    strS = strlen(str);
    substrS = strlen(substr);
    seedS = strlen(seed);

    //declare a __temp string variable
    char *__tmp = malloc(strS + 1);
    if(!__tmp){
        puts("memory allocation failed!");
        return NULL;
    }
    //calculate the size of string required to hold the replaced string and replace its occurence
    if(!recursive){
        size = strS + (seedS - substrS);
        __tmp = realloc(__tmp, size + 1);
        if(!__tmp)
            return NULL;
        //remove substr and store its index
        long ind = (long)(firstPos - str);
        strncpy(__tmp, str, ind);
        __tmp[ind] = '\0';
        strcat(__tmp, firstPos + substrS);
        if(!seedS)
            return __tmp;
        return insert(__tmp, seed, ind);
    }
        
    else if(recursive){
        //count the occurance of substr
        strcpy(__tmp, str);
        char* pos;
        while((pos = strstr(__tmp, substr))){
            size = strlen(__tmp) + (seedS - substrS);
            long ind = (long)(pos - __tmp);

            __tmp = realloc(__tmp, size + 1);
            char *__temp = malloc(size + 1);
            if(!__tmp || !__temp)
                return NULL;
            strcpy(__temp, __tmp);
            // printf(">%s\n",__tmp);
            strncpy(__tmp, __temp, ind);
            __tmp[ind] = '\0';
            // printf(">>%s\n",__tmp);
            strcat(__tmp, __temp + ind + substrS);
            // printf(">>>%s\n",__tmp);
            free(__temp);
            if(seedS){
                __temp = insert(__tmp, seed, ind);
                strcpy(__tmp, __temp);
                free(__temp);
            }   
        }
        return __tmp;
    }
    return NULL;
}

char *insert(char *str, char *sed, int index)
{
    int strl, sedl;
    strl = (int)strlen(str);
    sedl = (int)strlen(sed);
    char *dest = (char*)malloc(sizeof(char) * (strl + sedl +1));
    if(dest == NULL) return NULL;
    
    strncpy(dest, str, index );
    dest[index] = '\0';
    strcat(dest, sed);
    strcat(dest, str + index);
    return dest;
}

这里 test.py

from ast import Return
import subprocess as sp


tests = ["243 + 45*3 -43 + 45/9 + 6^6",
        "34 + 23 -54 + '6(76(32(56 + 45 -34(56- 34)) + 44)) *' 45 -7 ^ 5 -  4",
        "43 + 3.543 - 543.36 - 56.84*23.456 + 18/5 - '45.465(56 + 45 -34(59- 24))63.86' + 34",
        "5 ^ 3.543 - 543.36 - 56.84*23.456 + 18/5 - '45.465(56 + 45 -34(65- 41))63.86' + 3.345 ^ 4.65 + 456 - 29/3 ^ 2.34 - 11/4 ^ 3",
        '''23 + 345- 240*4 + '6+ 4 * 4' - '(5-2) / (4+ (5-3))' *6 + "45 - 23 +24 * (3+(4+3))
        +987543-45345+8635
        6453354 --"''',
    '''23*240*4 *'6+ 4 * 4 - (5-2)  (4+ (5-3))'  "45345 - 8(4+3) + 3(5-2)6 - (7+5)4 - 6(5+3^2)9 (5  *  4 -6)5 ^7" - 6 + "45 - 23 +24 * (3+(4+3))(6)"''',
        " '54( 34 + 34 - 23 + 34/12 + 3 ^4)'",
        " '5+54+( 34 + 34 - 23 + 256/16^2*8 + 34) - 32'",
        " '69( 31 + 4 - 23 + 72/6^2*8 + 34) - 32'",
        " '5+54+ 34 + 34 - 23 + (8) - 32'"
        ]

com = sp.run("gcc  calc.c replace.c -o calc -lm", shell = True, capture_output = True, text = True)
if (com.returncode):
    print(com.stderr)
    exit(0)

print("~~~Compiled Successfully~~~")
for test in tests:
    ret = sp.run("./calc " + test,shell=True, capture_output = True, text = True)
    if(ret.stderr):
        print(ret.stderr)
    else:
        print(ret.stdout)

一切正常，在文件替换中，c，（经过多次测试） 误差发生在函数

1. evaliutiate（）
2. 计算（）和
3. promate（） 在Calc.c文件中。