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.

Description Solution Video 15:40

227. Basic Calculator II

Medium47.3% acceptance32 companies

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 [-2³¹, 2³¹ - 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 * 10⁵
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, 2³¹ - 1].
The answer is guaranteed to fit in a 32-bit integer.