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
Pseudocode
- combination of using queues and recursion
- queue to push values in FIFO to be solved
- recursion to solve expression in brackets and return a value
- while also returning the index of where the calculation ended
- simplify equation to +ve, -ve numbers and return a single value via reduce.
Solution
// from solutions - python implementation
// https://leetcode.com/problems/basic-calculator/solutions/1456850/python-basic-calculator-i-ii-iii-easy-solution-detailed-explanation/
var calculate = function (s) {
let it = 0;
let num = 0;
let stack = [];
let sign = "+";
function update(op, v) {
console.log("update:", op, v);
if (op == "+") {
stack.push(v);
} else if (op == "-") {
stack.push(-v);
} else if (op == "*") {
stack.push(stack.pop() * v);
} else if (op == "/") {
stack.push(parseInt(stack.pop() / v));
}
console.log(stack);
}
while (it < s.length) {
console.log(stack);
let char = s[it];
if (/\d/.test(char)) {
num = num * 10 + parseInt(char);
} else if (char === "+" || char === "-" || char === "*" || char === "/") {
update(sign, num);
num = 0;
sign = char;
} else if (char === "(") {
const [val, idx] = calculate(s.slice(it + 1));
console.log("open parenthesis,", s.slice(it + 1), val, idx);
let j = idx;
num = val;
it = it + j;
} else if (char === ")") {
update(sign, num);
return [stack.reduce((prev, cur) => prev + cur), it + 1];
}
it += 1;
}
update(sign, num);
console.log(
stack,
"sum :",
stack.reduce((prev, cur) => prev + cur)
);
return stack.reduce((prev, cur) => prev + cur);
};
