Problem Description
Explanation
To solve this problem, we will use a stack to keep track of the operands and operators as we process the input expression. We will iterate through the string character by character and handle different cases such as digits, operators, and parentheses. By maintaining a running total and a sign value, we can calculate the result of the expression.
- Initialize a stack to store the operands and a variable
resultto store the final result. - Initialize
signas 1 to represent the positive sign. - Iterate through each character of the input string
s. - If the character is a digit, update the
numvariable. - If the character is an operator (+ or -), update the
resultandsignaccordingly. - If the character is an opening parenthesis, push the current
resultandsignonto the stack and reset them. - If the character is a closing parenthesis, calculate the result within the current parentheses and update the
resultandsignvalues. - Finally, return the calculated
result.
Time Complexity: O(n), where n is the length of the input string s.
Space Complexity: O(n), where n is the length of the input string s.
Solutions
class Solution {
public int calculate(String s) {
Stack<Integer> stack = new Stack<>();
int result = 0;
int num = 0;
int sign = 1;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
num = num * 10 + (c - '0');
} else if (c == '+') {
result += sign * num;
num = 0;
sign = 1;
} else if (c == '-') {
result += sign * num;
num = 0;
sign = -1;
} else if (c == '(') {
stack.push(result);
stack.push(sign);
result = 0;
sign = 1;
} else if (c == ')') {
result += sign * num;
num = 0;
result *= stack.pop(); // pop the sign
result += stack.pop(); // add back the result outside the parentheses
}
}
if (num != 0) {
result += sign * num;
}
return result;
}
}Related LeetCode Problems
Loading editor...