C++ 16ms recursive solution. Calculates with easy logic just like how human mind would do it.


  • 0
    F

    The idea is straight forward: simply calculate from left to right and add/subtract each number we meet (converting any parentheses into numbers by recursive calls). Here goes the code.

    class Solution {
    public:
       int calculate(std::string s) {
          if(s.empty()) return 0;
          s += ')'; int i=0;
          return calcInParentheses(s.data(), i);
       }
    private:
       // calc summation within a pair of parentheses given by its starting position
       int calcInParentheses(const char *s, int &i) {
          int res = 0; int sign = 1;
          while( true ) {
             while( s[i]==' ' ) ++i;          // skip spaces
             // recursive call when inner parenthese are met
             if(s[i]=='(') res += calcInParentheses(s, ++i)*sign;
             else res += getInt(s,i)*sign;    // add current int
             while( s[i]==' ' ) ++i;          // skip spaces
             if( s[i]==')' ) { ++i; break; }  // stop when given parentheses are done
             sign = s[i++]=='+'?1:-1;         // get next sign
          }
          return res;
       }
       int getInt(const char *s, int &i) {
          int res = 0;
          while( isdigit(s[i]) ) res = res*10 + s[i++]-'0';
          return res;
       }
    };
    
    

Log in to reply
 

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