Implement a basic calculator to evaluate the value of a simple string expression.

String expressions can contain opening parentheses (, closing parentheses), plus sign +, minus sign -, non negative integers and spaces.

Example 1:

Input: "1 + 1"
Output: 2
Example 2:

Input: "2-1 + 2"
Output: 3
Example 3:

Input: "(1 + (4 + 5 + 2) - 3) + (6 + 8)"
Output: 23
Explain:

You can assume that all the expressions given are valid.
Do not use the built-in library function eval.

#define true 1
#define false 0

int isDigit(char ch)
{
    if (ch >= '0' && ch <= '9') {
        return true;
    }
    return false;
}

int calculate(char *s)
{
    int len = strlen(s);
    int *stackDigit = (int*)malloc(sizeof(int) * len);
    char *stackOperator = (char*)malloc(sizeof(char) * len);
    int stackDigitTop = -1;
    int stackOperatorTop = -1;
    int i = 0;
    int tempDigit = 0;
    int num1 = 0;
    int num2 = 0;
    int temp = 0;
    for (i = 0; i < len; i++) {
        while (s[i] == ' ') {
            i++;
        }
        if (i == len) {
            break;
        }
        if (isDigit(s[i]) == true) {
            tempDigit = s[i] - '0';
            i++;
            while (isDigit(s[i]) == true) {
                tempDigit = tempDigit * 10 + (s[i] - '0');
                i++;
            }
            i--;
            stackDigitTop++;
            stackDigit[stackDigitTop] = tempDigit;
            while (stackOperatorTop != -1) {
                if (stackOperator[stackOperatorTop] == '+') {
                    num2 = stackDigit[stackDigitTop];
                    stackDigitTop--;
                    num1 = stackDigit[stackDigitTop];
                    stackDigitTop--;
                    temp = num1 + num2;
                    stackDigitTop++;
                    stackDigit[stackDigitTop] = temp;
                } else if (stackOperator[stackOperatorTop] == '-') {
                    num2 = stackDigit[stackDigitTop];
                    stackDigitTop--;
                    num1 = stackDigit[stackDigitTop];
                    stackDigitTop--;
                    temp = num1 - num2;
                    stackDigitTop++;
                    stackDigit[stackDigitTop] = temp;
                } else {
                    break;
                }
                stackOperatorTop--;
            }
            continue;
        } else if (s[i] == '(') {
            stackOperatorTop++;
            stackOperator[stackOperatorTop] = s[i];
        }  else if (s[i] == ')'){
            while (stackOperator[stackOperatorTop] != '(') {
                num2 = stackDigit[stackDigitTop];
                stackDigitTop--;
                num1 = stackDigit[stackDigitTop];
                stackDigitTop--;
                if (stackOperator[stackOperatorTop] == '+') {
                    temp = num1 + num2;
                    stackDigitTop++;
                    stackDigit[stackDigitTop] = temp;
                } else if (stackOperator[stackOperatorTop] == '-') {
                    temp = num1 - num2;
                    stackDigitTop++;
                    stackDigit[stackDigitTop] = temp;
                }
                stackOperatorTop--;
            }
            stackOperatorTop--;
        } else {
            if (stackOperatorTop != -1) {
                while (stackOperatorTop != -1) {
                    if (stackOperator[stackOperatorTop] == '+') {
                        num2 = stackDigit[stackDigitTop];
                        stackDigitTop--;
                        num1 = stackDigit[stackDigitTop];
                        stackDigitTop--;
                        temp = num1 + num2;
                        stackDigitTop++;
                        stackDigit[stackDigitTop] = temp;
                    } else if (stackOperator[stackOperatorTop] == '-') {
                        num2 = stackDigit[stackDigitTop];
                        stackDigitTop--;
                        num1 = stackDigit[stackDigitTop];
                        stackDigitTop--;
                        temp = num1 - num2;
                        stackDigitTop++;
                        stackDigit[stackDigitTop] = temp;
                    } else {
                        break;
                    }
                    stackOperatorTop--;
                }
            }
            stackOperatorTop++;
            stackOperator[stackOperatorTop] = s[i];
        }
    }
    while (stackOperatorTop != -1) {
        num2 = stackDigit[stackDigitTop];
        stackDigitTop--;
        num1 = stackDigit[stackDigitTop];
        stackDigitTop--;
        if (stackOperator[stackOperatorTop] == '+') {
            temp = num1 + num2;
            stackDigitTop++;
            stackDigit[stackDigitTop] = temp;
        } else if (stackOperator[stackOperatorTop] == '-') {
            temp = num1 - num2;
            stackDigitTop++;
            stackDigit[stackDigitTop] = temp;
        }
        stackOperatorTop--;
    }
    return stackDigit[0];
}