224. Basic Calculator
Problem Description
The problem tasks us with creating a program that can evaluate a string expression containing integers, '+', '-', '(', and ')', representing the addition and subtraction of integers as well as grouping with parentheses. No built-in functions or libraries for evaluating mathematical expressions are allowed. The objective is to parse and calculate the result of the given string as the expression would be evaluated in arithmetic.
Intuition
To solve this challenge, we simulate the mechanics of an arithmetic expression evaluator by manually parsing the string. This involves the following steps:
-
Linear Scanning: We process the string from left to right, character by character, to evaluate the numbers and the operators.
-
Dealing with Numbers: Since the numbers may have more than one digit, we need to convert the sequence of digit characters into actual numerical values. This is done by initializing a number
x
to0
and then for each digit'd'
we find, multiplyingx
by10
and addingd
tox
, effectively constructing the number in decimal. -
Handling Operators: We keep track of the last seen operator which will be either a '+' or a '-', through a
sign
variable which is1
or-1
, respectively. When a number is completely parsed, we combine it with the currentsign
to add or subtract from the accumulated answer. -
Using Stack for Parentheses: To evaluate expressions within parentheses, we use a stack. When we encounter an opening parenthesis '(', we push the current accumulated answer and the current sign onto the stack, then reset the answer and sign to begin evaluating the expression inside the parentheses. When we encounter a closing parenthesis ')', we pop the sign and the accumulated answer before the parenthesis from the stack, and combine them with the current answer inside the parentheses (apply the sign and then add the two numbers).
-
Final Computation: After we process all characters, the result of the entire expression will be in the
answer
variable. Parentheses are handled during the process as they are encountered, ensuring that the subexpressions are calculated at the correct times.
This approach systematically breaks down the string into components that we can evaluate in isolation, handling the precedence of operations in expressions with parentheses appropriately, leading to the correct final answer.
Solution Approach
The solution's approach primarily involves a while loop that iterates through the string s
, evaluating expressions and handling arithmetic operations and parentheses. The core components of the solution include:
-
Stack (
stk
): Used to store previous results and signs when an opening parenthesis is found. We push the currentans
andsign
and restart their values for evaluating the new embedded expression. -
Current answer (
ans
): This is the running total of the expression evaluated so far, excluding the content within parentheses which haven't been closed yet. When we find a closing parenthesis, we update it to include the result of expression inside the just-closed parenthesis. -
Current sign (
sign
): This variable holds the last seen sign of '+' or '-', initialized as1
(representing '+'). This is used to multiply with the current number found to add or subtract it fromans
. -
Index (
i
): To keep track of the current position within the string.
The algorithm proceeds as follows:
-
Iterate over each character in the string until the end is reached.
-
If a digit is encountered:
- A separate while loop gathers the entire number (as numbers could have multiple digits), constructing the value by multiplying the previously accumulated value by
10
and adding the digit to it. - After the whole number is determined, multiply it by the current
sign
and add it to the currentans
. - Update the index
i
to the position after the last digit of the number.
- A separate while loop gathers the entire number (as numbers could have multiple digits), constructing the value by multiplying the previously accumulated value by
-
When a '+' or '-' is encountered:
- The
sign
is updated to1
for '+' or-1
for '-'.
- The
-
On encountering an opening parenthesis '(':
- Push the current
ans
andsign
onto the stack (to 'remember' them for after the close parenthesis). - Reset
ans
andsign
for the next calculation within the new context (inside the parentheses).
- Push the current
-
On encountering a closing parenthesis ')':
- The expression inside the parenthesis is complete, so compute its value by multiplying it with the
sign
popped from the stack. - Then add the result to the
ans
before the parenthesis (also popped from the stack).
- The expression inside the parenthesis is complete, so compute its value by multiplying it with the
-
The loop increments the index
i
at each step, except when processing a whole number, wherei
is updated accordingly.
After the while loop completes, ans
contains the result of evaluating the entire expression, which is then returned.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use a simple expression to demonstrate the approach: 1 + (2 - (3 + 4))
.
- Initialize
ans = 0
,sign = 1
,stk = []
, and start at indexi = 0
. i = 0
: The first character is1
, a digit. So we form the number1
.- Update
ans
by adding1 * sign
which is1
. Nowans = 1
. i = 2
: The character is+
. Setsign
to1
.i = 4
: Encounter(
. Push the currentans
(1
) andsign
(1
) ontostk
and resetans
to0
,sign
to1
.i = 5
: Next is digit2
. Updateans
to2
.i = 7
: Encounter-
. Setsign
to-1
.i = 9
: Encounter(
again. Push the currentans
(2
) andsign
(-1
) ontostk
and resetans
to0
,sign
to1
.i = 10
: Digit3
is seen. Updateans
to3
.i = 12
: The character is+
. Setsign
to1
.i = 14
: Digit4
is seen. Updateans
by adding4 * sign
which is4
. Nowans = 3 + 4 = 7
.i = 15
: Encounter)
. Popstk
which has2
and-1
. Updateans
:ans = 2 - (7) = -5
.i
: Move forward to the next character, but there is none immediately after the closing parenthesis, so continue.i = 17
: Now, encounter another)
. Popstk
which has1
and1
. Updateans
:ans = 1 + (-5) = -4
.
At the end of the string, we have ans = -4
. Since we've processed every character according to the rules, and handled the nested parentheses correctly, the resultant ans
is the evaluation of the entire expression 1 + (2 - (3 + 4))
, which is indeed -4
.
Solution Implementation
1class Solution:
2 def calculate(self, s: str) -> int:
3 stack = [] # Initialize an empty list to be used as a stack
4 result, operator = 0, 1 # Initialize result to 0 and operator to 1 ('+' sign)
5 index, length = 0, len(s) # Initialize loop variables
6
7 # Iterate over the input string
8 while index < length:
9 # If the current character is a digit
10 if s[index].isdigit():
11 number = 0
12 # Continue until a non-digit is found, building the number
13 while index < length and s[index].isdigit():
14 number = number * 10 + int(s[index])
15 index += 1
16 # Update the result with the current number and the preceding operator
17 result += operator * number
18 # Compensate for the index increment in the loop
19 index -= 1
20 # If the current character is a plus, set operator to 1
21 elif s[index] == "+":
22 operator = 1
23 # If the current character is a minus, set operator to -1
24 elif s[index] == "-":
25 operator = -1
26 # Handle opening parentheses
27 elif s[index] == "(":
28 # Push the current result and operator to the stack
29 stack.append(result)
30 stack.append(operator)
31 # Reset the result and operator for the new expression within the parentheses
32 result, operator = 0, 1
33 # Handle closing parentheses
34 elif s[index] == ")":
35 # The result inside the parentheses is multiplied by the operator before the parentheses
36 result *= stack.pop()
37 # Add the result inside the parentheses to the result before the parentheses
38 result += stack.pop()
39 # Move to the next character
40 index += 1
41
42 return result # Return the evaluated result
43
1class Solution {
2 public int calculate(String s) {
3 // Stack to hold the intermediate results and signs
4 Deque<Integer> stack = new ArrayDeque<>();
5 // Initialize the sign as positive
6 int sign = 1;
7 // This will hold the final result of the evaluation
8 int result = 0;
9 // Length of the input string for iteration
10 int length = s.length();
11
12 // Iterating over each character in the string
13 for (int i = 0; i < length; ++i) {
14 char ch = s.charAt(i);
15 // Check if the current char is a digit
16 if (Character.isDigit(ch)) {
17 int startIndex = i;
18 int number = 0;
19 // Build the number till we encounter a non-digit
20 while (startIndex < length && Character.isDigit(s.charAt(startIndex))) {
21 number = number * 10 + s.charAt(startIndex) - '0';
22 startIndex++;
23 }
24 // Update the result with the current number and sign
25 result += sign * number;
26 // Move the pointer to the end of the number
27 i = startIndex - 1;
28 } else if (ch == '+') {
29 // Set sign as positive for addition
30 sign = 1;
31 } else if (ch == '-') {
32 // Set sign as negative for subtraction
33 sign = -1;
34 } else if (ch == '(') {
35 // Push the result and sign on the stack before the parenthesis
36 stack.push(result);
37 stack.push(sign);
38 // Reset result and sign for the expression inside the parenthesis
39 result = 0;
40 sign = 1;
41 } else if (ch == ')') {
42 // After closing parenthesis, result is the evaluated value inside the parenthesis
43 // Pop the sign before the parenthesis and multiply it with the current result,
44 // then add the result before the parenthesis
45 result = stack.pop() * result + stack.pop();
46 }
47 }
48 // Return the final result of the evaluation
49 return result;
50 }
51}
52
1class Solution {
2public:
3 int calculate(string s) {
4 stack<int> operands; // Stack to hold numbers and signs (as integer)
5 int result = 0; // Accumulator for the current result
6 int sign = 1; // Current sign, starts with positive
7 int n = s.size(); // Size of the input string
8
9 for (int i = 0; i < n; ++i) {
10 // If the character is a digit, it could be part of a multi-digit number.
11 if (isdigit(s[i])) {
12 int num = 0; // Initialize the number to be 0
13 // Construct the number from the subsequent digits
14 while (i < n && isdigit(s[i])) {
15 num = num * 10 + (s[i] - '0');
16 ++i;
17 }
18 // Add/Subtract the number to/from the current result
19 result += sign * num;
20 // Since the loop will increment i after, we decrease it here
21 --i;
22 } else if (s[i] == '+') {
23 sign = 1; // Set sign to positive for the next number
24 } else if (s[i] == '-') {
25 sign = -1; // Set sign to negative for the next number
26 } else if (s[i] == '(') {
27 // When encountering '(', push the current result and sign onto the stack
28 operands.push(result);
29 operands.push(sign);
30 // Reset result and sign for the new sub-expression inside the parentheses
31 result = 0;
32 sign = 1;
33 } else if (s[i] == ')') {
34 // Ending a sub-expression, pop sign from stack and multiply it with the current result
35 result *= operands.top();
36 operands.pop();
37 // Add the result of the sub-expression to the result up to the '('
38 result += operands.top();
39 operands.pop();
40 }
41 // Ignore whitespace and other non-math characters
42 }
43 return result; // Return the final result
44 }
45};
46
1function calculate(s: string): number {
2 const stack: number[] = [];
3 let currentSign = 1; // This will hold the current sign, 1 for '+' and -1 for '-'
4 let result = 0; // This will accumulate the result of the arithmetic expression
5 const length = s.length; // Length of the input string
6
7 // Iterate through each character of the input string
8 for (let i = 0; i < length; ++i) {
9 // Skip spaces in the expression
10 if (s[i] === ' ') {
11 continue;
12 }
13
14 // Update the sign for the next number
15 if (s[i] === '+') {
16 currentSign = 1;
17 } else if (s[i] === '-') {
18 currentSign = -1;
19 } else if (s[i] === '(') {
20 // Push the result and sign onto the stack before resetting them
21 stack.push(result);
22 stack.push(currentSign);
23 result = 0;
24 currentSign = 1;
25 } else if (s[i] === ')') {
26 // Pop the sign then the result from the stack and combine them
27 result *= stack.pop() as number;
28 result += stack.pop() as number;
29 } else {
30 // Parse the number and aggregate the result
31 let value = 0;
32 let j = i;
33 // Continue for all subsequent digits to form the full number
34 for (; j < length && !isNaN(Number(s[j])) && s[j] !== ' '; ++j) {
35 value = value * 10 + (s[j].charCodeAt(0) - '0'.charCodeAt(0));
36 }
37 result += currentSign * value;
38 i = j - 1; // Update the outer loop's index after processing the number
39 }
40 }
41
42 // Return the computed result
43 return result;
44}
45
Time and Space Complexity
Time Complexity
The time complexity of the code is determined by the number of operations needed to parse and evaluate the expression.
- Looping through each character in the input string
s
of lengthn
accounts forO(n)
because each character is considered exactly once. - Each digit in the string is processed and converted to an integer, which in the worst case, every character could be a digit, resulting in
O(n)
for the digit conversion process. - The operations related to stack (pushing and popping) occur in constant time
O(1)
for each operation, but in the worst case, the total time complexity for all such operations is proportional to the number of parentheses in the input string. Since parentheses pairs cannot exceedn/2
, the complexity due to stack operations is alsoO(n)
.
Therefore, the overall time complexity of the algorithm is O(n)
.
Space Complexity
The space complexity of the code is determined by the amount of additional memory needed to store intermediate results and the call stack (if applicable).
- The stack
stk
is used to store the result and sign at each level of parentheses, and in the worst case, where we have a pair of parentheses for every two characters (like "((...))"), the stack size could grow up ton/2
. Therefore, the space complexity due to the stack isO(n/2)
, which simplifies toO(n)
. - Variables
ans
,sign
,i
,x
,j
, andn
use a constant amount of space, contributingO(1)
.
Hence, the overall space complexity of the algorithm is O(n)
(where n
is the length of the string s
).
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following is a min heap?
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.