The Basic Calculator III problem asks you to implement a calculator that can evaluate a string expression containing non-negative integers, the operators +, -, *, /, and parentheses ( and ). The expression can have spaces, which should be ignored. You must respect the standard operator precedence: multiplication and division have higher precedence than addition and subtraction, and parentheses override precedence. The division should truncate toward zero.
s containing the arithmetic expression.eval() function.At first glance, this problem seems similar to parsing arithmetic expressions, but with the added challenge of handling nested parentheses and operator precedence. A brute-force approach might involve converting the expression into a postfix notation (Reverse Polish Notation) and then evaluating it, but that can be complex to implement, especially with nested parentheses.
Alternatively, we can process the string character by character and use a stack to manage numbers and operators. When we encounter an open parenthesis, we can recursively evaluate the sub-expression inside. Handling operator precedence is crucial: multiplication and division must be evaluated before addition and subtraction. By using a stack, we can defer addition and subtraction until all higher-precedence operations are handled.
The key is to process the expression in a single pass, using stacks to manage numbers and sub-expressions, and to apply operators as soon as their operands are known and precedence allows.
We will use a stack-based approach to evaluate the expression:
num to build multi-digit numbers and sign to track the most recent operator (default to '+').
(, recursively evaluate the sub-expression inside the parentheses.'+': Push num onto the stack.'-': Push -num onto the stack.'*': Pop the top of the stack, multiply by num, and push the result.'/': Pop the top of the stack, perform integer division by num (truncate toward zero), and push the result.sign to the current operator and reset num to zero.( is encountered, recursively call the evaluation function starting from the next character, and use the result as the current num. When a ) is encountered, return the sum of the stack up to that point.
This approach ensures that operator precedence and parentheses are handled correctly, and that the expression is evaluated in a single pass using recursion and stacks.
Consider the input: "2*(3+(4*5))"
num = 0, sign = +, stack = []2: num = 2*: Apply previous + sign, push 2 to stack. Set sign = *, num = 0(: Start evaluating sub-expression 3+(4*5)3: num = 3+: Apply + sign, push 3 to stack. Set sign = +, num = 0(: Start evaluating sub-expression 4*54: num = 4*: Apply + sign, push 4 to stack. Set sign = *, num = 05: num = 5* sign, pop 4 from stack, push 4*5 = 20[3, 20], sum is 23* sign, pop 2 from stack, push 2*23 = 46[46], sum is 46
The correct result is 46.
O(n) for conversion + O(n) for evaluation = O(n)O(n) for stack and output arraysO(n), since each character is processed onceO(n) for the stack and recursion stack (in the worst case, deeply nested parentheses)The optimized approach is efficient and suitable for expressions up to thousands of characters.
We tackled the Basic Calculator III problem by leveraging a stack-based approach with recursion to handle nested parentheses and operator precedence. By processing the expression in a single pass and applying operators as soon as their operands are ready, we efficiently evaluate even complex expressions. This method is both elegant and practical, demonstrating a powerful pattern for parsing and evaluating arithmetic expressions without relying on built-in evaluators.
class Solution:
def calculate(self, s: str) -> int:
def helper(it):
num = 0
stack = []
sign = '+'
while True:
try:
c = next(it)
except StopIteration:
break
if c == ' ':
continue
if c.isdigit():
num = num * 10 + int(c)
if c == '(':
num = helper(it)
if (not c.isdigit() and c != ' ') or c == ')':
if sign == '+':
stack.append(num)
elif sign == '-':
stack.append(-num)
elif sign == '*':
stack.append(stack.pop() * num)
elif sign == '/':
prev = stack.pop()
stack.append(int(prev / num))
num = 0
sign = c
if c == ')':
break
return sum(stack)
return helper(iter(s))
class Solution {
public:
int calculate(string s) {
int i = 0;
return helper(s, i);
}
private:
int helper(const string& s, int& i) {
stack<int> stk;
int num = 0;
char sign = '+';
for (; i < s.size(); ++i) {
char c = s[i];
if (c == ' ') continue;
if (isdigit(c)) {
num = num * 10 + (c - '0');
}
if (c == '(') {
++i;
num = helper(s, i);
}
if ((!isdigit(c) && c != ' ') || i == s.size() - 1 || c == ')') {
if (sign == '+') stk.push(num);
else if (sign == '-') stk.push(-num);
else if (sign == '*') {
int t = stk.top(); stk.pop();
stk.push(t * num);
}
else if (sign == '/') {
int t = stk.top(); stk.pop();
stk.push(t / num);
}
sign = c;
num = 0;
}
if (c == ')') break;
}
int res = 0;
while (!stk.empty()) {
res += stk.top();
stk.pop();
}
return res;
}
};
class Solution {
public int calculate(String s) {
int[] idx = new int[1];
return helper(s, idx);
}
private int helper(String s, int[] idx) {
Deque<Integer> stack = new ArrayDeque<>();
int num = 0;
char sign = '+';
while (idx[0] < s.length()) {
char c = s.charAt(idx[0]);
if (c == ' ') {
idx[0]++;
continue;
}
if (Character.isDigit(c)) {
num = num * 10 + (c - '0');
}
if (c == '(') {
idx[0]++;
num = helper(s, idx);
}
if (!Character.isDigit(c) && c != ' ' || idx[0] == s.length() - 1 || c == ')') {
if (sign == '+') stack.push(num);
else if (sign == '-') stack.push(-num);
else if (sign == '*') stack.push(stack.pop() * num);
else if (sign == '/') stack.push(stack.pop() / num);
sign = c;
num = 0;
}
if (c == ')') {
idx[0]++;
break;
}
idx[0]++;
}
int res = 0;
while (!stack.isEmpty()) res += stack.pop();
return res;
}
}
var calculate = function(s) {
let i = 0;
function helper() {
let stack = [];
let num = 0;
let sign = '+';
while (i < s.length) {
let c = s[i];
if (c === ' ') {
i++;
continue;
}
if (/\d/.test(c)) {
num = num * 10 + parseInt(c);
}
if (c === '(') {
i++;
num = helper();
}
if ((isNaN(parseInt(c)) && c !== ' ') || i === s.length - 1 || c === ')') {
if (sign === '+') stack.push(num);
else if (sign === '-') stack.push(-num);
else if (sign === '*') stack.push(stack.pop() * num);
else if (sign === '/') stack.push(parseInt(stack.pop() / num));
sign = c;
num = 0;
}
if (c === ')') {
i++;
break;
}
i++;
}
return stack.reduce((a, b) => a + b, 0);
}
return helper();
};