Basic Calculator III

Basic Calculator III is a Hard 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

You are given a string s representing a valid mathematical expression. The expression may contain non-negative integers, the operators '+', '-', '', '/', parentheses '(', ')', and spaces.

Evaluate the expression and return its result as an integer.

Note that integer division should truncate toward zero. You are not allowed to use any built-in function that evaluates strings as mathematical expressions (such as eval()).

Constraints: - 1 <= s.length <= 10^4 - s consists of digits, operators '+', '-', '', '/', parentheses '(', ')', and spaces. - The given expression is always valid.

Return the integer result of evaluating the expression.

Topics and companies

Topics: Math, String, Stack, Recursion.

Reported in interviews at Facebook, Amazon, ByteDance.

How to practise Basic Calculator III on Thita.ai

Starter code is provided in 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 III in the code editor, or read the Basic Calculator III editorial for a worked solution with its approach and complexity analysis.

Where Basic Calculator III 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 III

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

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