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().

&nbsp;
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


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 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.


```class Solution:
    def calculate(self, s: str) -> int:
        curr,output,sign,stack = 0,0,1,[]

        for ch in s:
            if ch.isdigit():
                curr = curr * 10 + int(ch)

            elif ch == '+':
                output += sign * curr
                sign = 1
                curr = 0

            elif ch == '-':
                output += sign * curr
                sign = -1
                curr = 0

            elif ch == '(':
                #push the result and then the sign
                stack.append(output)
                stack.append(sign)
                sign = 1
                output = 0

            elif ch == ')':
                output += sign * curr
                output *= stack.pop()
                output += stack.pop()
                curr = 0
        return output + sign*curr``
class Solution {
    int idx; // this index traverse the string in one pass, between different level of recursion
    public int calculate(String s) {
        idx = 0; // Initialization should be here
        return helper(s);
    }
    
    private int helper(String s) {
        int res = 0, num = 0, preSign = 1, n = s.length();
        while (idx < n) {
            char c = s.charAt(idx++);
            if (c == '(') num = helper(s); // Let recursion solve the sub-problem
            else if (c >= '0' && c <= '9') num = num * 10 + c - '0';
            if (c == '+' || c == '-' || c == ')' || idx == n) { // we need one more calculation when idx == n
                res += preSign * num;
                if (c == ')') return res; // end of a sub-problem
                num = 0;
                preSign = c == '+' ? 1 : -1;
            }
        }
        return res;
    }
}
class Solution {
public:
   int calculate(string s) {
       stack<pair<int,int>> st; // pair(prev_calc_value , sign before next bracket () )
       
       long long int sum = 0;
       int sign = +1;
       
       for(int i = 0 ; i < s.size() ; ++i)
       {
           char ch = s[i];
           
           if(isdigit(ch))
           {
               long long int num = 0;
               while(i < s.size() and isdigit(s[i]))
               {
                   num = (num * 10) + s[i] - '0';
                   i++;
               }
               i--; // as for loop also increase i , so if we don't decrease i here a sign will be skipped
               sum += (num * sign);
               sign = +1; // reseting sign
           }
           else if(ch == '(')
           {
               // Saving current state of (sum , sign) in stack
               st.push(make_pair(sum , sign));
               
               // Reseting sum and sign for inner bracket calculation
               sum = 0; 
               sign = +1;
           }
           else if(ch == ')')
           {
               sum = st.top().first + (st.top().second * sum);
               st.pop();
           }
           else if(ch == '-')
           {
               // toggle sign
               sign = (-1 * sign);
           }
       }
       return sum;
   }
};
var calculate = function(s) {

	const numStack = [[]];
	const opStack = [];

	const isNumber = char => !isNaN(char);

	function calculate(a, b, op){
		if(op === '+') return a + b;
		if(op === '-') return a - b;
	}

	let number = '';
	for (let i = 0; i < s.length; i++) {
		const char = s[i];

		if (char === ' ') continue;

		if (isNumber(char)) {
			number += char;
			continue;
		}

		if(number) { // i.e. char is not a number so the number has ended
			if (numStack[numStack.length - 1].length === 0) {
				numStack[numStack.length - 1].push(+number);
			} else {
				const a = numStack[numStack.length - 1].pop();
				const op = opStack.pop();
				numStack[numStack.length - 1].push(calculate(a, +number, op));
			}

			number = '';
		}

		if (char === '(') {
			if (numStack[numStack.length - 1].length === 0) {
				numStack[numStack.length - 1].push(0);
				opStack.push('+');
			}

			numStack.push([]); // Start a new stack for this parenthesis
			continue;
		}

		if (char === ')') {
			const b = numStack.pop().pop();
			const a = numStack[numStack.length - 1].pop();
			const op = opStack.pop();
			numStack[numStack.length - 1].push(calculate(a, b, op));
			continue;
		}

		if (char === '+' || char === '-') {
			if (numStack[numStack.length - 1].length === 0) {
				numStack[numStack.length - 1].push(0);
			}

			opStack.push(char);
			continue;
		}


		// We should never reach here
		throw new Error('Unexpected input: ' + char);
	}

	if(number){
		if (numStack[numStack.length - 1].length === 0) return +number;

		const a = numStack[numStack.length - 1].pop();
		const op = opStack.pop();
		numStack[0].push(calculate(a, +number, op));
	}

	return numStack.pop().pop();
};
Basic Calculator