Basic Calculator II

Basic Calculator II is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Stack Patterns pattern, in the Expression Evaluation (RPN/Infix) subpattern.

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+22" 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.

Topics and companies

Topics: Math, String, Stack.

Reported in interviews at Amazon, Facebook, Microsoft, Roblox, Snapchat, Uber.

How to practise Basic Calculator II on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(n) space.

Open Basic Calculator II in the code editor, or read the Basic Calculator II editorial for a worked solution with its approach and complexity analysis.

Where Basic Calculator II sits in the DSA pattern sheet

• Stack Patterns pattern guide
• Expression Evaluation (RPN/Infix) subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Basic Calculator II

Other problems that use the same Expression Evaluation (RPN/Infix) and Stack Patterns techniques:

• Basic Calculator — Hard, same subpattern
• Basic Calculator III — Hard, same subpattern
• Evaluate Reverse Polish Notation — Medium, same subpattern
• Asteroid Collision — Medium, same pattern
• Daily Temperatures — Medium, same pattern
• Decode String — Medium, same pattern