A simple, clean solution accepted as best submission in C, well-explained


  • 0

    Since the input string is always valid, so what we truly need to concern about is that handling process and in this process only the sign is the essence; here so we are about to use a stack to store the signs before opening bracket which can change the signs inside brackets. Our rule is as follows:

    • encountering digits, just collect them for calculation;
    • encountering '+' or '-', check the stack for its sign before opening bracket and calculate and update the sign for next number;
    • encountering '(', aha, its opening bracket, so we need to store the sign to stack and reset the current sign to '+' since we consider both sign and sign in stack to determine the sign and then calculate; still confused? okay, suppose "1-(5+3)" the minus will be converted to plus if we don't reset sign to plus here;
    • encountering ')', delete the top sign in stack and then calculate;
    • at last, after we traversing the string there might be some number left un-calculated, so we need to check it and calculate&&.

    Done! End of story!

    • Space cost O(n)
    • Time cost O(n)

    //AC - 4ms;
    int calculate(char* s)
    {
        int* signs = (int*)malloc(sizeof(int)); //used to store the signs before opening bracket;
        int top = -1;
        signs[++top] = 1;
        int sign = 1;
        int num = 0;
        int ret = 0; //used to store the result;
        while(*s)
        {
            if(*s>='0' && *s<='9')  //collect the number between non-digits;
            {
                num = 10*num + *s - '0';
            }
            else if(*s=='+' || *s=='-') //add the previous number and reset sign;
            {
                ret += signs[top]*sign*num;
                num = 0;
                sign = (*s=='+'? 1 : -1);
            }
            else if(*s == '(') //store the sign before opening bracket;
            {
                signs = (int*)realloc(signs, sizeof(int)*(top+2));
                signs[top+1] = sign*signs[top]; //to avoid evaluation sequence problem, moving top++ to another statement;
                top++;
                sign = 1;
            }
            else if(*s == ')') //add the previous number and delete a sign for this pair of brackets;
            {
                ret += signs[top--]*sign*num;
                num = 0;
            }
            s++;
        }
        if(num) //if there is still number left;
            ret += signs[top]*sign*num;
        return ret;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.