class Solution:
def calculate(self, s: str) -> int:
stack = []
result = 0
number = 0
sign = 1
i = 0
while i < len(s):
char = s[i]
if char.isdigit():
number = 0
while i < len(s) and s[i].isdigit():
number = number * 10 + int(s[i])
i += 1
result += sign * number
continue
elif char == '+':
sign = 1
elif char == '-':
sign = -1
elif char == '(':
stack.append(result)
stack.append(sign)
result = 0
sign = 1
elif char == ')':
prev_sign = stack.pop()
prev_result = stack.pop()
result = prev_result + prev_sign * result
i += 1
return result
class Solution {
public:
int calculate(string s) {
stack<int> stk;
int result = 0, number = 0, sign = 1;
for (int i = 0; i < s.size(); ++i) {
char c = s[i];
if (isdigit(c)) {
number = 0;
while (i < s.size() && isdigit(s[i])) {
number = number * 10 + (s[i] - '0');
++i;
}
result += sign * number;
--i;
} else if (c == '+') {
sign = 1;
} else if (c == '-') {
sign = -1;
} else if (c == '(') {
stk.push(result);
stk.push(sign);
result = 0;
sign = 1;
} else if (c == ')') {
int prev_sign = stk.top(); stk.pop();
int prev_result = stk.top(); stk.pop();
result = prev_result + prev_sign * result;
}
}
return result;
}
};
class Solution {
public int calculate(String s) {
Stack<Integer> stack = new Stack<>();
int result = 0, number = 0, sign = 1;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
number = 0;
while (i < s.length() && Character.isDigit(s.charAt(i))) {
number = number * 10 + (s.charAt(i) - '0');
i++;
}
result += sign * number;
i--;
} else if (c == '+') {
sign = 1;
} else if (c == '-') {
sign = -1;
} else if (c == '(') {
stack.push(result);
stack.push(sign);
result = 0;
sign = 1;
} else if (c == ')') {
int prevSign = stack.pop();
int prevResult = stack.pop();
result = prevResult + prevSign * result;
}
}
return result;
}
}
var calculate = function(s) {
let stack = [];
let result = 0, number = 0, sign = 1;
for (let i = 0; i < s.length; i++) {
let c = s[i];
if (/\d/.test(c)) {
number = 0;
while (i < s.length && /\d/.test(s[i])) {
number = number * 10 + parseInt(s[i]);
i++;
}
result += sign * number;
i--;
} else if (c === '+') {
sign = 1;
} else if (c === '-') {
sign = -1;
} else if (c === '(') {
stack.push(result);
stack.push(sign);
result = 0;
sign = 1;
} else if (c === ')') {
let prevSign = stack.pop();
let prevResult = stack.pop();
result = prevResult + prevSign * result;
}
}
return result;
};
The Basic Calculator problem asks you to evaluate a mathematical expression string containing non-negative integers, the operators '+' (addition), '-' (subtraction), parentheses '(' and ')', and spaces. The expression is always valid, meaning it is properly formed and has no invalid characters or mismatched parentheses.
s representing the expression.s.--5), and you do not need to consider multiplication or division.At first glance, the problem seems similar to evaluating a simple arithmetic expression. However, the presence of parentheses introduces the need to handle nested calculations and operator precedence. If we approach this naively, we might consider evaluating the string from left to right, but parentheses mean we must sometimes "pause" the current calculation, compute a sub-expression, and then resume.
The brute-force approach would be to convert the expression to postfix notation (Reverse Polish Notation) and then evaluate it, but this is unnecessarily complex for only + and - operators. Instead, we can take advantage of the limited operators and use a stack to handle changes in context when we encounter parentheses.
The key insight is to track the current result and sign as we parse the string. When we hit a '(', we save the current state on a stack and start a new calculation for the sub-expression. When we hit a ')', we finish the sub-expression and combine it with the previous context. This way, we never have to build an explicit tree or convert to postfix.
The solution uses a stack and a few variables to keep track of the current calculation context. Here is a step-by-step breakdown:
result: The running total of the current context.sign: The current sign (+1 or -1) to apply to the next number.stack: Used to store the previous result and sign when we encounter a '('.result using the current sign.'+', set sign to +1 for the next number.'-', set sign to -1 for the next number.'(':
result and sign onto the stack.result to 0 and sign to 1 to start a new sub-expression.')':
sign and result from the stack.result by the sign, and add it to the previous result.This approach is efficient and leverages the stack to handle nested expressions cleanly.
Let's walk through the input: s = "1 + (2 - (3 + 4))"
result = 0, sign = 1, stack = []result += 1 * 1 = 1sign = 1result (1) and sign (1) onto stack. Reset result = 0, sign = 1result += 1 * 2 = 2sign = -1result (2) and sign (-1) onto stack. Reset result = 0, sign = 1result += 1 * 3 = 3sign = 1result += 1 * 4 = 7sign (-1) and result (2) from stack. result = 2 + (-1) * 7 = -5sign (1) and result (1) from stack. result = 1 + 1 * (-5) = -4
The final answer is -4.
Brute-force Approach:
The stack is only used to store context at each parenthesis, and all other variables use constant space.
The Basic Calculator problem is elegantly solved by using a stack to handle nested parentheses and context switching. By keeping track of the current result and sign, and pushing/popping context when parentheses are encountered, we can efficiently evaluate the expression in a single pass. This approach avoids the overhead of building a syntax tree or converting to postfix, and works efficiently for arbitrarily nested valid expressions using only addition and subtraction.