#227

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Basic Calculator II

Basic Calculator II evaluates a mathematical expression with operators and integers, handling basic arithmetic with precedence using stack-based state management.

math string stack

Problem Statement

Given a string representing a valid arithmetic expression, your task is to evaluate the expression and return the result as an integer. Operators include addition, subtraction, multiplication, and division. You must correctly manage operator precedence without relying on traditional parentheses. The division operator truncates the result toward zero.

The string will consist of integers and operators, with spaces separating the tokens. All the integers are non-negative and fall within the range [0, 231 - 1]. The expression is guaranteed to be valid, and the result will fit within a 32-bit integer.

Examples

Example 1

Input: s = "3+2*2"

Output: 7

Example details omitted.

Example 2

Input: s = " 3/2 "

Output: 1

Example details omitted.

Example 3

Input: s = " 3+5 / 2 "

Output: 5

Example details omitted.

Constraints

1 <= s.length <= 3 * 105
s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.
s represents a valid expression.
All the integers in the expression are non-negative integers in the range [0, 231 - 1].
The answer is guaranteed to fit in a 32-bit integer.

Solution Approach

Stack-based Approach

Using a stack to manage intermediate results is key. As you traverse the expression, handle the current operator and number while updating the stack accordingly. Addition and subtraction will directly push values onto the stack, while multiplication and division require modifying the most recent number on the stack.

Operator Precedence Handling

Handle multiplication and division first as they have higher precedence. After processing these, add or subtract the numbers to calculate the final result. This step ensures the proper sequence of operations without requiring explicit parentheses.

Efficient Parsing

To avoid excessive space usage, process the string in a single pass. While parsing, maintain the current number and operator, updating the stack as needed. Handle spaces by skipping them and continue processing until the entire expression is evaluated.

Complexity Analysis

Metric	Value
Time	\mathcal{O}(n)
Space	\mathcal{O}(1)

The time complexity is O(n) since we process each character of the string exactly once. Space complexity is O(1) as the stack only holds a few integers at a time, ensuring minimal space usage relative to the input size.

What Interviewers Usually Probe

Test the candidate's understanding of operator precedence and state management using a stack.
Evaluate how the candidate handles parsing and tokenizing the string efficiently.
Check how well the candidate handles edge cases such as division by zero or handling spaces.

Common Pitfalls or Variants

Common pitfalls

Incorrect handling of operator precedence, especially when mixing addition, subtraction, multiplication, and division.
Failing to update the stack correctly during multiplication and division.
Not properly handling negative numbers or white spaces.

Follow-up variants

Modify the problem to include parentheses and evaluate the expression accordingly.
Handle floating point numbers instead of integers in the expression.
Add additional operators like modulo or exponentiation.

FAQ

How does Basic Calculator II handle operator precedence?

Basic Calculator II solves operator precedence by handling multiplication and division first using the stack, then adding or subtracting the results.

What are the key challenges in solving Basic Calculator II?

The main challenges include managing operator precedence and ensuring that spaces are properly handled, while efficiently evaluating the expression.

Can GhostInterview help me practice the Basic Calculator II problem?

Yes, GhostInterview offers problem-solving exercises with feedback on stack-based problems like Basic Calculator II to improve your skills.

How does the stack help in Basic Calculator II?

The stack helps by storing intermediate results, allowing you to correctly handle operations with different precedences as you evaluate the expression.

What space complexity is required for Basic Calculator II?

The space complexity is O(1), as the stack only needs to store a limited number of integers at a time.

terminal

Solution

Solution 1: Stack

We traverse the string $s$, and use a variable `sign` to record the operator before each number. For the first number, its previous operator is considered as a plus sign. Each time we traverse to the end of a number, we decide the calculation method based on `sign`:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def calculate(self, s: str) -> int:
        v, n = 0, len(s)
        sign = '+'
        stk = []
        for i, c in enumerate(s):
            if c.isdigit():
                v = v * 10 + int(c)
            if i == n - 1 or c in '+-*/':
                match sign:
                    case '+':
                        stk.append(v)
                    case '-':
                        stk.append(-v)
                    case '*':
                        stk.append(stk.pop() * v)
                    case '/':
                        stk.append(int(stk.pop() / v))
                sign = c
                v = 0
        return sum(stk)

Continue Practicing

#224 basic calculator #770 basic calculator iv #241 different ways to add parentheses