String calculator in C with recursion

Question

I am making a string calculator in C, but i have some problems.

for example: 2 * (123-321) * (2+(3-4)-(3*2*2)) / ((12-2)/(1+1+1+1+0+ 1))

should print 2178, but instead it prints 3058704.

So i tried calculating (2+(3-4)-(3*2*2)) and found it returns 77578153 instead of -11.
And also 2*(123-321)*(1-12)/2 returns 1980 instead of 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

any help would be appreciated.

Answer 1

As Klas Lindbäck has already pointed out, your code has problems when you parse constructs in parentheses.

In principle, your algorithm should be something like this:

• If there are operators outside parentheses, find the one with the lowest precedence (that is a plus or minus rather than a times or div) and split the expression there, recursing left and right.
• Otherwise, when the first and last characters are parentheses, remove them and recurse with the contents.
• Otherwise, the result must be a number: Parse it.

You can check for unbalanced parentheses or non-numbers on the way.

Applying this algoriithm to your code gives:

#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;
}

This will yield 1980, not 2178, because somwhere on the way you divide −11 by 2, which is −5 and not −5.5, owing to integer division.

By treating an empty string as zero, this code will even treat unary minus and plus as 0 - x. (Of course, there's also unary times now, which is nonsensical.)

Finally, if you are open to alternative approaches, the Shunting-yard algorithm evaluates expressions in a single pass from left to right.

Answer 2

Your problem seems to occur when there are multiple layers of parenthesis in the input.

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

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

This line looks suspicious:

            while(!oklepaj1 == zaklepaj1) {

! has higher precedence than == so you probably mean:

            while(!(oklepaj1 == zaklepaj1)) {

I tried it, and it still doesn't calculate correctly when there are multiple layers of parenthesis in the input, so there are more bugs related to parenthesis.

Edit:

I found the remaining problem with parenthesis. When you encounter a parenthesis you send the entire expression in the parenthesis to charToDigit. Instead, you should send what's inside a set of parenthesis to rekurzija.

Also, you are using integer division, so any remainder is dropped. That is why 1/2*2 gives 0.