Skip to main content
Talentd

Basic Calculator II - Solution & Explanation

MediumMathStringStack21 min readAsked at: Amazon, Microsoft, Apple +29
Practice this problem

Problem Statement

Given a string s which represents an expression, evaluate this expression and return its value. 

The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

 

Example 1:

Input: s = "3+2*2"
Output: 7

Example 2:

Input: s = " 3/2 "
Output: 1

Example 3:

Input: s = " 3+5 / 2 "
Output: 5

 

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.

Approach Overview

Problem Overview: You receive a string representing a mathematical expression containing non‑negative integers and the operators +, -, *, and /. Spaces may appear anywhere. The goal is to evaluate the expression while respecting normal operator precedence (multiplication and division before addition and subtraction).

Approach 1: Use a Stack to Handle Precedence (O(n) time, O(n) space)

This approach scans the string once while building numbers and applying operations as they appear. Keep a stack of intermediate values and track the previous operator. When you finish reading a number, decide what to do based on the last operator: push the number for +, push its negative for -, or pop the top element and immediately compute multiplication or division for * and /. Multiplication and division are resolved immediately, which naturally preserves precedence.

After processing the entire string, sum the values in the stack to produce the final result. Each character is processed once, and each stack operation is constant time. This method is straightforward and mirrors how expression evaluation works conceptually, making it common in stack-based parsing problems involving string expressions.

Approach 2: Two-Pass Parsing Using Sign Tracking (O(n) time, O(1) space)

This approach removes the explicit stack and instead tracks the last computed term. Iterate through the string while building the current number and remembering the previous operator. Maintain two variables: result for the accumulated sum and lastTerm for the most recent value that may still be affected by multiplication or division.

When encountering + or -, add lastTerm to result and start a new term with the current number (positive or negative). For * and /, update lastTerm directly by multiplying or dividing it with the current number. This delays addition until the correct precedence is guaranteed. The algorithm still scans the expression once, but it stores only a few integers, achieving constant auxiliary space.

This technique relies on careful state tracking rather than a container, making it slightly more optimized for memory. It still requires parsing integers from the string and handling truncating division according to problem rules. Problems combining arithmetic evaluation with math parsing often use this pattern.

Recommended for interviews: The stack-based approach is the most widely expected answer because it clearly demonstrates how you enforce operator precedence during a single pass. After presenting that solution, mentioning the constant-space sign-tracking optimization shows deeper understanding of expression parsing and algorithmic refinement.

Approach 1: Approach 1: Use a Stack to Handle Precedence

This approach uses a stack to store numbers and consider operator precedence. Multiplication and division are processed immediately, whereas addition and subtraction modify how numbers are pushed onto the stack.

This C solution iterates over the string, calculates numeric values, updates the stack with results immediately for '*', '/', while '+' and '-' add or subtract the number to/from the stack respectively. Finally, calculates the sum of values in the stack.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) where n is the length of the string. Space Complexity: O(n) for storing numbers in the stack.

Try this approach in the editor →

Approach 2: Approach 2: Two-Pass Parsing Using Sign Tracking

This approach parses the expression twice, first to handle multiplications and divisions, then to process additions and subtractions. This avoids using a stack and simplifies sign handling.

This C code tracks the last number while parsing. It processes multiplication and division without using an additional stack by altering the last number, collects results using '+' and '-', and accumulates a final result.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) where n is the number of characters in the input string. Space Complexity: O(1) since it only uses primitive data types.

Try this approach in the editor →

Approach 3: 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:

  • Plus sign: push the number into the stack;
  • Minus sign: push the opposite number into the stack;
  • Multiplication and division signs: calculate the number with the top element of the stack, and replace the top element of the stack with the calculation result.

After the traversal ends, the sum of the elements in the stack is the answer.

The time complexity is O(n), and the space complexity is O(n), where n is the length of the string s.

Code

PythonJavaC++GoC#

Python

Java

C++

Go

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Use a Stack to Handle Precedence

Time Complexity: O(n) where n is the length of the string. Space Complexity: O(n) for storing numbers in the stack.

Approach 2: Two-Pass Parsing Using Sign Tracking

Time Complexity: O(n) where n is the number of characters in the input string. Space Complexity: O(1) since it only uses primitive data types.

Stack—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Stack to Handle PrecedenceO(n)O(n)General case; easiest to reason about when evaluating expressions with operator precedence.
Two-Pass Parsing with Sign TrackingO(n)O(1)When optimizing memory or demonstrating deeper understanding of expression parsing.

Video Solution

BASIC CALCULATOR II | LEETCODE 227 | PYTHON SOLUTION • Cracking FAANG • 47,330 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Basic Calculator II easy or hard?
Basic Calculator II is considered a medium difficulty problem. The challenge is not the arithmetic itself but correctly handling operator precedence while parsing a string. Once you understand the stack pattern for expression evaluation, the implementation becomes straightforward.
Basic Calculator II Python/Java solution
Python and Java implementations both follow the same logic: iterate through the string, build numbers, track the previous operator, and apply stack operations when an operator or end of string appears. Python typically uses a list as the stack, while Java uses a Stack or ArrayDeque.
How to solve Basic Calculator II in O(n)?
Scan the string once while building numbers and tracking the previous operator. Use a stack or a lastTerm variable to immediately evaluate multiplication and division, while delaying addition and subtraction until the end. Each character is processed once and each arithmetic operation is constant time, resulting in O(n) complexity.
What is the best approach for Basic Calculator II?
The most common approach uses a stack to enforce operator precedence while scanning the expression once. Numbers are pushed for addition and subtraction, while multiplication and division immediately update the top stack value. This keeps the evaluation correct without needing full expression parsing. The algorithm runs in O(n) time and O(n) space.
Is Basic Calculator II asked at Google/Amazon/Meta?
Expression evaluation problems like Basic Calculator II appear in interviews at companies such as Amazon, Google, and Meta because they test string parsing, operator precedence handling, and careful state management. Variations of calculator problems are common in backend and systems interviews.
What data structure is used in Basic Calculator II?
A stack is the primary data structure used in the common solution. It stores intermediate values so multiplication and division can be applied immediately while addition and subtraction are deferred. Some optimized solutions replace the stack with variables that track the last evaluated term.
What is the time complexity of Basic Calculator II?
Basic Calculator II can be solved in O(n) time where n is the length of the string. The algorithm scans the expression once, builds numbers, and performs constant-time operations for each operator. Both the stack approach and the optimized sign-tracking method achieve linear time complexity.

Ready to solve this problem?

Practice Basic Calculator II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Basic Calculator

Next

Basic Calculator III