Problem
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 * 105sconsists of digits,'+','-','(',')', and' '.srepresents 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
/**
* @param {string} s
* @return {number}
*/
var calculate = function(s) {
var res = 0;
var i = 0;
var isPlus = true;
while (i < s.length) {
switch (s[i]) {
case ' ':
i++;
break;
case '+':
isPlus = true;
i++;
break;
case '-':
isPlus = false;
i++;
break;
case '(':
i++;
var num = 0;
var from = i;
while (!(num === 0 && s[i] === ')')) {
if (s[i] === '(') num++;
if (s[i] === ')') num--;
i++;
}
isPlus
? (res += calculate(s.slice(from, i)))
: (res -= calculate(s.slice(from, i)))
i++;
break;
default:
var num = Number(s[i]);
while (s[i + 1] >= '0' && s[i + 1] <= '9') {
i++;
num *= 10;
num += Number(s[i]);
}
isPlus ? (res += num) : (res -= num);
i++;
break;
}
}
return res;
};
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(1).