Is Basic Calculator III easy or hard?

Basic Calculator III is rated Hard because it combines multiple concepts: string parsing, operator precedence, stack-based evaluation, and nested parentheses. While each idea is manageable individually, implementing them together correctly requires careful control flow and edge case handling.

Basic Calculator III Python/Java solution

In Python or Java, the common solution iterates through the string, builds numbers, and uses a stack to apply operators based on precedence. When encountering parentheses, a recursive helper evaluates the sub-expression and returns its result. The algorithm remains O(n) time and O(n) space across languages.

How to solve Basic Calculator III in O(n)?

Scan the expression from left to right while building numbers and tracking the previous operator. Use a stack to store intermediate values: push numbers for + and -, and immediately compute multiplication or division with the stack top. When encountering parentheses, recursively evaluate the inner expression and treat the result as a number. Every character is processed once, giving O(n) time.

What is the best approach for Basic Calculator III?

The best approach uses a stack combined with recursion to evaluate expressions while scanning the string once. Numbers are pushed to a stack and multiplication or division is computed immediately, while addition and subtraction are accumulated later. Parentheses trigger recursive evaluation of sub-expressions. This solution runs in O(n) time with O(n) space.

Is Basic Calculator III asked at Google/Amazon/Meta?

Expression evaluation and calculator-style parsing problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants such as Basic Calculator I, II, and III test understanding of stacks, recursion, and operator precedence handling.

What data structure is used in Basic Calculator III?

The primary data structure is a stack. It stores intermediate numbers while operators determine how values are combined. Recursion is often used alongside the stack to evaluate expressions inside parentheses.

What is the time complexity of Basic Calculator III?

The optimal solution runs in O(n) time where n is the length of the expression string. Each character is processed once while building numbers or applying operators. Stack operations are constant time, so the overall complexity remains linear with O(n) auxiliary space.

Description Solution Video 19:25

772. Basic Calculator III

Hard53.2% acceptance16 companiesPremium elsewhere, free here

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, '+', '-', '*', '/' operators, and open '(' and closing parentheses ')'. 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 = "1+1"
Output: 2

Example 2:

Input: s = "6-4/2"
Output: 4

Example 3:

Input: s = "2*(5+5*2)/3+(6/2+8)"
Output: 21

Constraints:

1 <= s <= 10⁴
s consists of digits, '+', '-', '*', '/', '(', and ')'.
s is a valid expression.

Asked at 16 companies

Intuit Pocket Gems Hulu Houzz Jingchi Verkada Tiktok Snapchat DoorDash Coupang Motive Microsoft

+4 more

Google Amazon Oracle Meta

Topics

19:25

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

772. Basic Calculator III

Asked at 16 companies

Topics

Similar problems