Leetcode Study Day 28

Basic Calculator

Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:

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

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

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

Constraints:

1 <= s.length <= 3 * 105
s consists of digits, '+', '-', '(', ')', and ' '.
s represents a valid expression.
'+' is not used as a unary operation (i.e., "+1" and "+(2 + 3)" is invalid).
'-' could be used as a unary operation (i.e., "-1" and "-(2 + 3)" is valid).
There will be no two consecutive operators in the input.
Every number and running calculation will fit in a signed 32-bit integer.

Solution

I found a recursive solution to solve this probelm. then main idea is use a recursive function to get the result from the start of the string to the end or the ‘)’ character. It first find the number between operators, then it add the number with the sign to the result value, then it reset the number to 0. If it finds a ‘(‘, it calls the recursive function again to get the result of the expression inside the ‘()’. If it finds a ‘+’, it sets the sign to 1, if it finds a ‘-‘, it sets the sign to -1. If it finds a ‘)’, it returns the result value.

#include <cctype>
class Solution {
public:
    int calculate(string s) {
        int i = 0, N = s.size();
        return dfs(s, i, N);
    }
    
    int dfs(const string& s, int& i, const int& N){
        int res = 0, sign = 1, num = 0;
        while(i < N && s[i] != ')'){
            if(isdigit(s[i]))
                num = num * 10 + (s[i] - '0');
            else{
                res += sign * num;
                num = 0;
                if(s[i] == '+') sign = 1;
                else if(s[i] == '-') sign = -1;
                else if(s[i] == '('){
                    i++;
                    res = res + sign * dfs(s, i, N);
                }
            }
            i++;
        }
        return res + sign * num;
    }
};