Basic Calculator — LeetCode 224 Python Solution
HardStackRecursionMathString
- Problem
- #224
- Pattern
- Stack
- Reading time
- 5 min
- Source
- leetcode.com
The problem
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
- Input
- s = "1 + 1"
- Output
- 2
Python solution
Python
class Solution:
def calculate(self, s: str) -> int:
stk = []
ans, sign = 0, 1
i, n = 0, len(s)
while i < n:
if s[i].isdigit():
x = 0
j = i
while j < n and s[j].isdigit():
x = x * 10 + int(s[j])
j += 1
ans += sign * x
i = j - 1
elif s[i] == "+":
sign = 1
elif s[i] == "-":
sign = -1
elif s[i] == "(":
stk.append(ans)
stk.append(sign)
ans, sign = 0, 1
elif s[i] == ")":
ans = stk.pop() * ans + stk.pop()
i += 1
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n), where n is the length of the string s auxiliary |
Pattern: Stack
When the most recent unresolved thing is the one that matters, use a stack. LeetCode 224. Basic Calculator is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Stack.
The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.
Related problems
On study lists
This problem is on Grind 75 and Top Interview 150.
Frequently asked questions
- How hard is LeetCode 224. Basic Calculator?
- LeetCode 224. Basic Calculator is rated Hard on LeetCode.
- What is the time complexity of LeetCode 224. Basic Calculator?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 224. Basic Calculator?
- The Python solution on this page uses O(n), where n is the length of the string s auxiliary space.
- What topics does LeetCode 224. Basic Calculator cover?
- LeetCode 224. Basic Calculator is tagged Stack, Recursion, Math and String on LeetCode.