带递归的 C 中的字符串计算器

Question

我正在用 C 语言制作一个字符串计算器，但遇到了一些问题。

例如：2 * (123-321) * (2+(3-4)-(3*2*2)) / ((12-2)/(1+1+1+1+0+ 1))

应该打印 2178，但它却打印 3058704.

所以我尝试计算 (2+(3-4)-(3*2*2)) 并发现它 returns 77578153 而不是 -11.
还有 2*(123-321)*(1-12)/2 returns 1980 而不是 2178.

#include <stdio.h>
#include <stdlib.h>
char *vnos;

int charToDigit(int i1, int i2) {
    int stevilo = 0;
    int i;
    //printf("%d  %d\n",i1,i2);
   // printf("%c %d\n",vnos[i1], vnos[i1]);
    for(i=i1; i<=i2; i++)
        //printf("%d  ", (vnos[i1]-48));
         stevilo = (stevilo + (vnos[i] - '0'))*10;
    stevilo = stevilo/10;
    return stevilo;
}

int rekurzija(int zacetek, int konec) {
     //printf("bumbum: %d %d \n", zacetek, konec);
    int i,oklepaj1,zaklepaj1,oklepaj,zaklepaj;
    int zacasniI=0;
    i=zacetek;

    if(vnos[zacetek] == '(' && vnos[konec] == ')'){
        oklepaj = 1;
        zaklepaj = 0;
        i++;
        while(!oklepaj == zaklepaj) {
            if (vnos[i] == '(')
                oklepaj++;
            if (vnos[i] == ')')
                zaklepaj++;
            i++;
        }
        i--;
        if(i==konec){
            return rekurzija(zacetek+1,konec-1);
        }
    }


    for(i=zacetek; i<=konec; i++){
           // printf("tralala: %d %d \n", zacetek, konec);
        switch(vnos[i]){
            case '+':
                return rekurzija(zacetek,(i-1))+rekurzija((i+1),konec);
            case '-':
                if(i>zacasniI)
                    zacasniI = i;
                break;
            case '*':
                if(zacasniI==0)
                    zacasniI = i;
                break;
            case '/':
                if(zacasniI==0 || vnos[zacasniI]=='/')
                    zacasniI = i;
                break;
            case '(':
                oklepaj1 = 1;
                zaklepaj1 = 0;
                i++;
                while(!oklepaj1 == zaklepaj1) {
                if (vnos[i] == '(')
                    oklepaj1++;
                if (vnos[i] == ')')
                    zaklepaj1++;
                i++;
                }
                i--;
                break;
        }

    }
    if(zacasniI>0){
        switch(vnos[zacasniI]) {
        case '-': return rekurzija(zacetek, zacasniI-1)-rekurzija(zacasniI+1, konec);
        case '*': return rekurzija(zacetek, zacasniI-1)*rekurzija(zacasniI+1, konec);
        case '/': return rekurzija(zacetek, zacasniI-1)/rekurzija(zacasniI+1, konec);
        }
    }

    return charToDigit(zacetek,konec);

}

int main(){
    vnos = malloc(sizeof(char) * 9000);
    char r;
    int z = 0;
    int l;
    scanf("%c", &r);
    while(r != '\n'){
        if(r != ' '){
            vnos[z] = r;
            z++;
        }
        scanf("%c", &r);
    }
    int result = rekurzija(0,z-1);
    printf("%d\n", result);
    return 0;
}

vnos = input
zacetek = start
konec = end
stevilo = number
oklepaj = right parenthesis
zaklepaj = left parenthesis
zacasni = temporary

如有任何帮助，我们将不胜感激。

Answer 1

当输入中有多层括号时，您的问题似乎会出现。

(2+(3-4)-(3*2*2)) --> fail

2+(3-4)-(3*2*2) --> -11  correct

这一行看起来很可疑：

            while(!oklepaj1 == zaklepaj1) {

! 的优先级高于 == 所以你的意思可能是：

            while(!(oklepaj1 == zaklepaj1)) {

我试过了，在输入多层括号的情况下还是不能正确计算，所以括号相关的bug比较多

编辑：

我发现了括号的剩余问题。当遇到括号时，将括号中的整个表达式发送到 charToDigit。相反，您应该将一组括号内的内容发送到 rekurzija.

此外，您使用的是整数除法，因此任何余数都将被删除。这就是 1/2*2 给出 0 的原因。

Answer 2

正如 Klas Lindbäck 已经指出的那样，当您解析括号中的结构时，您的代码会出现问题。

原则上你的算法应该是这样的：

如果 ide 括号外有运算符，找到优先级最低的（即加号或减号而不是时间或 div）并在那里拆分表达式，向左递归并且正确。
否则，当第一个和最后一个字符是括号时，将它们移除并递归内容。
否则，结果必须是一个数字：解析它。

您可以在途中检查不平衡的括号或非数字。

将此算法应用于您的代码可得到：

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

char *vnos = "2*(123-321)*(2+(3-4)-(3*2*2))/((12-2)/(1+1+1+1+0+1))";

int charToDigit(int i1, int i2)
{
    int stevilo = 0;
    int i;

    for(i = i1; i <= i2; i++) {
        int n = vnos[i] - '0';

        if (n < 0 || n > 9) return -1;
        stevilo = 10 * stevilo + n;
    }

    return stevilo;
}

int prec(int op)
{
    switch (op) {
    case '+':   return 1;
    case '-':   return 1;
    case '*':   return 2;
    case '/':   return 2;
    }

    return 0;
}

int calc(int op, int a, int b)
{
    switch (op) {
    case '+':   return a + b;
    case '-':   return a - b;
    case '*':   return a * b;
    case '/':   if (b == 0) {
                    printf("Division by zero\n");
                    exit(1);
                }
                return a / b;
    }

    return 0;
}

int rekurzija(int zacetek, int konec)
{
    int oklepaj = 0;
    int mid = -1;
    int i;

    if (zacetek > konec) return 0;

    for(i = zacetek; i <= konec; i++) {
        int c = vnos[i];

        if (c == '(') {
            oklepaj++;
        } else if (c == ')') {
            if (oklepaj == 0) {
                printf("Bad zaklepaj in %.*s\n", 
                    konec - zacetek + 1, vnos + zacetek);
                exit(1);
            }
            oklepaj--;
        } else if (oklepaj == 0) {            
            int n = prec(c);

            if (n && (mid < 0 || n < prec(vnos[mid]))) {
                mid = i;
            }
        }
    }

    if (oklepaj > 0) {
        printf("Bad uklepaj in %.*s\n", 
            konec - zacetek + 1, vnos + zacetek);
        exit(1);
    }

    if (mid >= 0) {
            int a = rekurzija(zacetek, mid - 1);
            int b = rekurzija(mid + 1, konec);   
            int res =  calc(vnos[mid], a, b);

            printf("%d %c %d == %d\n", a, vnos[mid], b, res);
            return res;
    } else {
        if (vnos[zacetek] == '(' && vnos[konec] == ')'){
            return rekurzija(zacetek + 1, konec - 1);
        }

        int res = charToDigit(zacetek, konec);

        if (res < 0) {
            printf("Bad stevilo in %.*s\n", 
                konec - zacetek + 1, vnos + zacetek);
            exit(1);
        } else {
            return res;
        }
    }

    return 0;
}

int main()
{
    int result = rekurzija(0, strlen(vnos) - 1);

    printf("%d\n", result);

    return 0;
}

这将产生 1980，而不是 2178，因为在某个地方你 divide −11 乘以 2，即 −5 而不是 −5.5，因为整数 div愿景。

通过将空字符串视为零，此代码甚至会将一元减号和加号视为 0 - x。（当然，现在也有一元时间，这是无稽之谈。）

最后，如果您对其他方法持开放态度，Shunting-yard algorithm 从左到右一次计算表达式。

带递归的 C 中的字符串计算器

String calculator in C with recursion

c

string

recursion

calculator