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 * 10^5sconsists 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 (Java)
class Solution {
private int i = 0;
public int calculate(String s) {
char[] ca = s.toCharArray();
return helper(ca);
}
private int helper(char[] ca) {
int num = 0;
int prenum = 0;
boolean isPlus = true;
for (; i < ca.length; i++) {
char c = ca[i];
if (c != ' ') {
if (c >= '0' && c <= '9') {
if (num == 0) {
num = (c - '0');
} else {
num = num * 10 + c - '0';
}
} else if (c == '+') {
prenum += num * (isPlus ? 1 : -1);
isPlus = true;
num = 0;
} else if (c == '-') {
prenum += num * (isPlus ? 1 : -1);
num = 0;
isPlus = false;
} else if (c == '(') {
i++;
prenum += helper(ca) * (isPlus ? 1 : -1);
isPlus = true;
num = 0;
} else if (c == ')') {
return prenum + num * (isPlus ? 1 : -1);
}
}
}
return prenum + num * (isPlus ? 1 : -1);
}
}
Solution (Javascript)
/**
* @param {string} s
* @return {number}
*/
var calculate = function(s) {
let stack = []
let num = 0
let sign = 1
let res = 0
for (let i = 0; i < s.length; i++) {
let char = s.charAt(i)
if (char >= '0' && char <= '9') {
num = num * 10 + parseInt(char, 10)
} else if (char === '+') {
res += sign * num
sign = 1
num = 0
} else if (char === '-') {
res += sign * num
sign = -1
num = 0
} else if (char === '(') {
stack.push(res)
stack.push(sign)
sign = 1
res = 0
num = 0
} else if (char === ')') {
res += sign * num
res *= stack.pop()
res += stack.pop()
num = 0
}
}
return res + sign * num
};
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).