LeetCode224——Basic Calculator

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open 

(

 and closing parentheses 

)

, the plus 

+

 or minus sign 

-

, non-negative integers and empty spaces 

.

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23
      

Note: Do not use the 

eval

 built-in library function.

實作：

        void skipws(string &s, int * beg, bool b = false)

    {

        if (b) {

            while (s[*beg] == ' ') {

                (*beg)++;

            }

        } else {

            while (s[*beg] == ' ' || s[*beg] == '(' || s[*beg] == ')') {

                (*beg)++;

            }

        }

    }

    int numend(string &s, int beg)

    {

        while (s[beg] >= '0' && s[beg] <= '9') {

            beg++;

        }

        return beg;

    }

    int parenthesisend(string& s, int beg){

        int brace = 0;

        while (s[beg] != ')' || brace != 0) {

            if (s[beg] == '(') {

                brace++;

            } else if (s[beg] == ')') {

                brace--;

            }

            beg++;

        }

        return beg;

    }

    int calculate(string s) {

        int start = 0;

        int result = 0;

        while (start < s.size()) {

            skipws(s, &start);

            if (s[start] == '+') {

                start++;

                skipws(s, &start);

                int end = numend(s, start);

                result += atoi(s.substr(start, end-start).c_str());

                start = end;

            } else if (s[start] == '-') {

                start++;

                skipws(s, &start, true);

                if (s[start] == '(') {

                    start++;

                    int end = parenthesisend(s, start);

                    result -= calculate(s.substr(start, end-start));

                    start = end+1;

                }

                else {

                    int end = numend(s, start);

                    result -= atoi(s.substr(start, end-start).c_str());

                    start = end;

                }

            } else {

                int end = numend(s, start);

                result = atoi(s.substr(start, end-start).c_str());

                start = end;

            }

            skipws(s, &start);

        }

        return result;

    }