224. Basic Calculator

HardStackRecursionMathString
Leetcode Link

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:

  1. Linear Scanning: We process the string from left to right, character by character, to evaluate the numbers and the operators.

  2. 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 to 0 and then for each digit 'd' we find, multiplying x by 10 and adding d to x, effectively constructing the number in decimal.

  3. Handling Operators: We keep track of the last seen operator which will be either a '+' or a '-', through a sign variable which is 1 or -1, respectively. When a number is completely parsed, we combine it with the current sign to add or subtract from the accumulated answer.

  4. 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).

  5. 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.

Learn more about Stack, Recursion and Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

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 current ans and sign 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 as 1 (representing '+'). This is used to multiply with the current number found to add or subtract it from ans.

  • 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 current ans.
    • Update the index i to the position after the last digit of the number.

  • When a '+' or '-' is encountered:

    • The sign is updated to 1 for '+' or -1 for '-'.

  • On encountering an opening parenthesis '(':

    • Push the current ans and sign onto the stack (to 'remember' them for after the close parenthesis).
    • Reset ans and sign for the next calculation within the new context (inside the parentheses).

  • 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 loop increments the index i at each step, except when processing a whole number, where i is updated accordingly.

After the while loop completes, ans contains the result of evaluating the entire expression, which is then returned.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Example Walkthrough

Let's use a simple expression to demonstrate the approach: 1 + (2 - (3 + 4)).

  1. Initialize ans = 0, sign = 1, stk = [], and start at index i = 0.
  2. i = 0: The first character is 1, a digit. So we form the number 1.
  3. Update ans by adding 1 * sign which is 1. Now ans = 1.
  4. i = 2: The character is +. Set sign to 1.
  5. i = 4: Encounter (. Push the current ans (1) and sign (1) onto stk and reset ans to 0, sign to 1.
  6. i = 5: Next is digit 2. Update ans to 2.
  7. i = 7: Encounter -. Set sign to -1.
  8. i = 9: Encounter ( again. Push the current ans (2) and sign (-1) onto stk and reset ans to 0, sign to 1.
  9. i = 10: Digit 3 is seen. Update ans to 3.
  10. i = 12: The character is +. Set sign to 1.
  11. i = 14: Digit 4 is seen. Update ans by adding 4 * sign which is 4. Now ans = 3 + 4 = 7.
  12. i = 15: Encounter ). Pop stk which has 2 and -1. Update ans: ans = 2 - (7) = -5.
  13. i: Move forward to the next character, but there is none immediately after the closing parenthesis, so continue.
  14. i = 17: Now, encounter another ). Pop stk which has 1 and 1. Update ans: 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
Not Sure What to Study? Take the 2-min Quiz：

Which type of traversal does breadth first search do?

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 length n accounts for O(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 exceed n/2, the complexity due to stack operations is also O(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 to n/2. Therefore, the space complexity due to the stack is O(n/2), which simplifies to O(n).
  • Variables ans, sign, i, x, j, and n use a constant amount of space, contributing O(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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following shows the order of node visit in a Breadth-first Search?

Recommended Readings

Stack Intro

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 Review

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 Basics

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 Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫