227. Basic Calculator II

MediumStackMathString
Leetcode Link

Problem Description

The problem requires us to evaluate a mathematical expression given as a string. The expression includes integers and the operators '+', '-', '*', and '/'. We need to process the expression and return the result as an integer. The division operation should truncate the result toward zero, meaning it should not result in any fractional part. We need to handle the expression correctly, keeping in mind the different precedence of the operators: multiplication and division have higher precedence over addition and subtraction.

All the numbers and the result of the computation are guaranteed to be within the range of a 32-bit signed integer. It is also worth noting that the given expression will be valid, so there is no need to handle any syntax errors.

Additionally, it is important to mention that we cannot use any built-in functions that can evaluate strings as mathematical expressions directly, such as the eval() function in Python.

Intuition

To solve this problem, we need to implement an algorithm that can parse and evaluate the expression respecting the correct operator precedence. Since we can't use built-in evaluation functions, we have to simulate the calculation manually. One common approach to evaluating expressions is to use a stack.

Here’s the intuition behind using a stack in this solution:

  1. When we encounter a number, we store it for the next operation.
  2. When we encounter an operator, we decide what to do based on the previous operator.
  3. For '+' or '-', we need to add or subtract the number to/from our result. But since multiplication and division have higher precedence, we cannot directly add/subtract the number – we push it onto the stack.
  4. For '*' or '/', we immediately perform the operation with the previous number because they have higher precedence.
  5. Updating the current operator as we go allows us to know which operation to perform next.

To achieve the evaluation:

  • We iterate over the string.
  • We keep track of the current number and the last operator we have seen.
  • When we see a new operator, we perform the necessary operation based on the last operator, which could mean pushing to the stack or popping from the stack, performing an operation, and then pushing back the result.
  • At the end of the expression, we perform the operation for the last seen operator.
  • Since all numbers and results are within the range of a signed 32-bit integer, we do not need to worry about overflow.

After traversing the entire string and performing all stack operations, the result of the expression will be the sum of all numbers present in the stack.

Learn more about Stack and Math patterns.

Solution Approach

The implementation follows these steps, making use of a stack and a variable to keep track of the current number (initially 0) and another to remember the last operator (initially '+'):

  1. Initialize Variables: A stack stk is used to handle the numbers and the intermediate results. The variable v is used to build the current number as we parse the string. Another variable, sign, stores the last encountered operator, which is initially set to '+'.

  2. Parse the String: The string s is parsed character by character using a for loop. If the current character c is a digit, it's a part of the current number v. We update v by shifting the current value by one digit to the left (multiplying by 10) and adding the digit (v * 10 + int(c)).

  3. Handle Operators and End of String: We need to perform an action whenever we encounter an operator or the end of the string (because the last number might not be followed by an operator). So we check if the character c is in '+-*/', or if it is the last character in the string (i == n - 1).

  4. Perform Operations Based on Last Sign:

    • If the last sign was '+', push the current value of v onto the stack.
    • If it was '-', push the negative of v onto the stack.
    • If it was '*', pop the top value from the stack, multiply it by v, and push the result back onto the stack.
    • If it was '/', pop the top value from the stack, truncate divide it by v, and push the result back onto the stack. This is achieved by using int(stk.pop() / v) which truncates towards zero in Python.

    After processing the current number and operator, sign is updated to the current operator c, and v is reset to 0 to hold the next number.

  5. Evaluate the Stack: After the loop is finished, all values left in the stack are parts of the expression where addition and subtraction should be applied. As we pushed the results of multiplications and divisions and also considered the sign for addition and subtraction, simply summing all the values in the stack using sum(stk) gives us the final result.

The function finally returns the sum of all elements in the stack, which is the evaluated result of the given expression.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example to illustrate the solution approach by evaluating the expression s = "3+5*2-4/2" step by step.

  1. Initialize Variables: We start by initializing our stack stk, our variable v to 0, and our operator variable sign to '+'.

  2. Parse the String: We parse each character of our string s.

    • For the first character '3', since it is a digit, we update v to be v * 10 + 3, which is 3.
    • The next character is '+'. Since we encounter an operator, we perform the action for the last sign ('+'). We push 3 onto the stack (as our v is 3 and the sign is '+'). We then update sign to '+', and reset v to 0.

  3. Continue parsing:

    • Next, we encounter '5', which we multiply by 10 and add to our v (0 at this moment), resulting in 5.
    • Similarly, we encounter the character '2' after '5' and the '*' operator, but we don't do anything yet because the number 2 is not complete. After '2', our current v is 52.
    • Then we see the '*' operator. Now we need to act on the previous sign which was '+', so we push 5 into our stack and reset v to 2 because 2 is part of the next operation which involves multiplication. We update sign to be '*'.

  4. Handle Operators and End of String:

    • Continue parsing: next, we encounter '-', and since our last operator was '*', we multiply the most recent number in the stack (5) by v (which is 2), and push the result 10 back onto the stack. Update sign to '-' and v to 0.
    • Parsing the next number '4', just increment v to 4.
    • We see the '/' operator, which means—since the last sign was '-'—we push -4 onto the stack. Update sign to '/' and reset v to 0.
    • Lastly, the character '2' sets v to 2.

  5. At this point, we've reached the end of the string. The last operator is '/', so we must divide the top value of the stack -4 by v, which is 2, truncate towards zero, and push the result back to the stack (-2).

  6. Evaluate the Stack: We now evaluate the contents of the stack, which has [3, 10, -2]. By summing them up, we get the final result of 3 + 10 - 2 = 11.

    # Stack operations in detail:
# stk = [] after initialization
# stk = [3] after processing "3+"
# stk = [3, 5] after processing "5"
# stk = [10] after processing "5*2"
# stk = [10, -4] after processing "-4"
# stk = [10, -2] after processing "-4/2" (since the division truncates towards zero)
# Final sum of stack = 3 + 10 - 2 = 11

The above step-by-step processing adheres to the operator precedence and accurately evaluates the mathematical expression without the use of any built-in evaluators. The final result for the expression s = "3+5*2-4/2" is 11.

Solution Implementation

1class Solution:
2    def calculate(self, s: str) -> int:
3        # Initialize the value to hold current number and stack to store values.
4        value, n = 0, len(s)
5        # Set the initial sign to '+' (plus).
6        sign = '+'
7        # Initialize an empty stack to keep numbers and intermediate results.
8        stack = []
9
10        # Iterate over each character in the input string.
11        for i, char in enumerate(s):
12            # If the character is a digit, update 'value' to be the current multi-digit number.
13            if char.isdigit():
14                value = value * 10 + int(char)
15          
16            # If we reach the end of the string or encounter an operator.
17            if i == n - 1 or char in '+-*/':
18                # Perform an action depending on the last sign observed.
19                if sign == '+':
20                    # If the sign is plus, push the current value onto the stack.
21                    stack.append(value)
22                elif sign == '-':
23                    # If the sign is minus, push the negative of the value onto the stack.
24                    stack.append(-value)
25                elif sign == '*':
26                    # If the sign is times, multiply the top of the stack by the current value and push it back.
27                    stack.append(stack.pop() * value)
28                elif sign == '/':
29                    # If the sign is divide, take the top of the stack, divide by current value and push the result back.
30                    # Use integer division to round towards zero.
31                    stack.append(int(stack.pop() / value))
32              
33                # Update the sign to the current operator.
34                sign = char
35                # Reset 'value' for the next number.
36                value = 0
37      
38        # The final result is the sum of the values in the stack.
39        return sum(stack)
40
1import java.util.Deque;
2import java.util.ArrayDeque;
3
4class Solution {
5    public int calculate(String s) {
6        Deque<Integer> stack = new ArrayDeque<>(); // Use a stack to manage intermediate results
7        char operation = '+'; // Initialize the operation as addition
8        int value = 0; // This will hold the current number
9      
10        // Iterate through each character in the input string
11        for (int i = 0; i < s.length(); ++i) {
12            char currentChar = s.charAt(i);
13          
14            // If the current character is a digit, accumulate into value
15            if (Character.isDigit(currentChar)) {
16                value = value * 10 + (currentChar - '0');
17            }
18          
19            // If we've reached the end of the string or we encounter an operator
20            if (i == s.length() - 1 || currentChar == '+' || currentChar == '-' 
21                                      || currentChar == '*' || currentChar == '/') {
22              
23                // Perform the operation based on the previous sign
24                switch (operation) {
25                    case '+':
26                        stack.push(value); // Add the value to the stack
27                        break;
28                    case '-':
29                        stack.push(-value); // Push the negated value for subtraction
30                        break;
31                    case '*':
32                        stack.push(stack.pop() * value); // Multiply with the top value on the stack
33                        break;
34                    case '/':
35                        stack.push(stack.pop() / value); // Divide the top value with current value
36                        break;
37                }
38              
39                operation = currentChar; // Update the operation for the next iteration
40                value = 0; // Reset value for the next number
41            }
42        }
43      
44        int result = 0; // Initialize result to accumulate stack values
45        // Pop values from the stack and add them to calculate the result
46        while (!stack.isEmpty()) {
47            result += stack.pop();
48        }
49      
50        return result; // Return the final calculated result
51    }
52}
53
1#include <cctype>
2#include <stack>
3#include <string>
4
5class Solution {
6public:
7    int calculate(std::string s) {
8        // Initialize the current value and the total size of the string
9        int currentValue = 0, stringSize = s.size();
10        // Set the initial sign to '+'
11        char operationSign = '+';
12        // Stack to hold intermediate results
13        std::stack<int> calculationStack;
14        for (int i = 0; i < stringSize; ++i) {
15            char currentChar = s[i];
16            // If character is a digit, build the number by multiplying the current value by 10 and adding the digit's integer value
17            if (std::isdigit(currentChar)) currentValue = currentValue * 10 + (currentChar - '0');
18            // If we reach the end of the string or encounter an operation 
19            if (i == stringSize - 1 || currentChar == '+' || currentChar == '-' || currentChar == '*' || currentChar == '/') {
20                switch (operationSign) {
21                    // If the sign is '+', push the current value to the stack
22                    case '+':
23                        calculationStack.push(currentValue);
24                        break;
25                    // If the sign is '-', push the negative of the current value to the stack
26                    case '-':
27                        calculationStack.push(-currentValue);
28                        break;
29                    // If the sign is '*', multiply the top element of the stack with the current value and push the result back to the stack
30                    case '*':
31                        {
32                            int topValue = calculationStack.top();
33                            calculationStack.pop();
34                            calculationStack.push(topValue * currentValue);
35                        }
36                        break;
37                    // If the sign is '/', divide the top element of the stack by the current value and push the result back to the stack
38                    case '/':
39                        {
40                            int topValue = calculationStack.top();
41                            calculationStack.pop();
42                            calculationStack.push(topValue / currentValue);
43                        }
44                        break;
45                }
46                // Update the operation sign for the next operation
47                operationSign = currentChar;
48                // Reset the current value
49                currentValue = 0;
50            }
51        }
52        // Initialize the answer to 0
53        int result = 0;
54        // Add up all values in the stack to get the final result
55        while (!calculationStack.empty()) {
56            result += calculationStack.top();
57            calculationStack.pop();
58        }
59        // Return the result of expression evaluation
60        return result;
61    }
62};
63
1// Import Stack data structure for use in calculation
2import { Stack } from "typescript-collections";
3
4// Function to evaluate the arithmetic expression within a string
5function calculate(expression: string): number {
6    // Initialize currentValue to hold the numbers as they are parsed
7    let currentValue: number = 0;
8    // Determine the length of the expression string
9    let expressionSize: number = expression.length;
10    // Start with a default operationSign of '+'
11    let operationSign: string = '+';
12    // Use a stack to keep track of calculation results
13    let calculationStack = new Stack<number>();
14
15    for (let i = 0; i < expressionSize; ++i) {
16        let currentChar = expression[i];
17
18        // If the current character is a digit, construct the number
19        if (!isNaN(parseInt(currentChar))) {
20            currentValue = currentValue * 10 + (parseInt(currentChar));
21        }
22
23        // Perform operations at the end of the string or at an operator
24        if (i === expressionSize - 1 || currentChar === '+' || currentChar === '-' || currentChar === '*' || currentChar === '/') {
25            switch (operationSign) {
26                // Push current value to stack for a '+' operation
27                case '+':
28                    calculationStack.push(currentValue);
29                    break;
30                // Push the negative of current value for a '-' operation
31                case '-':
32                    calculationStack.push(-currentValue);
33                    break;
34                // Multiply the stack's top with current value for a '*' operation
35                case '*':
36                    {   
37                        let topValue = calculationStack.pop();
38                        if(topValue !== undefined) {
39                            calculationStack.push(topValue * currentValue);
40                        }
41                    }
42                    break;
43                // Divide the stack's top by current value for a '/' operation
44                case '/':
45                    {
46                        let topValue = calculationStack.pop();
47                        if(topValue !== undefined) {
48                            calculationStack.push(Math.trunc(topValue / currentValue));
49                        }
50                    }
51                    break;
52            }
53            // Update the operationSign with current character
54            operationSign = currentChar;
55            // Reset currentValue for the next part of the string
56            currentValue = 0;
57        }
58    }
59
60    // Calculate the final result by summing up the values in the stack
61    let result: number = 0;
62    while (!calculationStack.isEmpty()) {
63        let value = calculationStack.pop();
64        if(value !== undefined) {
65            result += value;
66        }
67    }
68
69    // Return the result of the expression evaluation
70    return result;
71}
72
73// Note: Since this bit of code uses the 'Stack' implementation from the 'typescript-collections' library,
74// you would have to install that npm package to use this stack data structure.
75

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(n) where n is the length of the input string. The algorithm iterates through each character of the string exactly once, and the operations within the loop are constant time operations, including digit extraction, basic arithmetic operations, and stack manipulation. The final summation of stack elements also takes O(n) time in the worst case where all characters result in individual numbers pushed onto the stack.

Space Complexity

The space complexity is O(n) for the stack that stores numbers based on the operations. In the worst case, where the string is composed of numbers separated by addition signs, each number is pushed onto the stack, reaching a maximum stack size proportional to the length of the input string.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

The three-steps of Depth First Search are:

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

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

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

LeetCode Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More