Basic Calculator
Basic Calculator 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
Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.
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 = " 2-1 + 2 " Output: 3
Example 3:
Input: s = "(1+(4+5+2)-3)+(6+8)" Output: 23
Constraints:
- 1 <= s.length <= 3 105
- s consists of digits, '+', '-', '(', ')', and ' '.
- s represents a valid expression.
- '+' is not used as a unary operation (i.e., "+1" and "+(2 + 3)" is invalid).
- '-' could be used as a unary operation (i.e., "-1" and "-(2 + 3)" is valid).
- There will be no two consecutive operators in the input.
- Every number and running calculation will fit in a signed 32-bit integer.
Topics and companies
Topics: Math, String, Stack, Recursion.
Reported in interviews at Amazon, Roblox, Facebook, Indeed, Karat, Microsoft, Google, ByteDance, Uber, Wish.
How to practise Basic Calculator 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), where n is the length of the input string. Each character is processed at most once. time and O(n), in the worst case due to the stack storing up to O(n) elements for deeply nested parentheses. space.
Open Basic Calculator in the code editor, or read the Basic Calculator editorial for a worked solution with its approach and complexity analysis.
Where Basic Calculator 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
Other problems that use the same Expression Evaluation (RPN/Infix) and Stack Patterns techniques:
- Basic Calculator II — Medium, 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