Implement basic calculator
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Take-home Project
##### Question
LeetCode 227. Basic Calculator II – implement an arithmetic expression evaluator supporting +, -, *, / and integer operands
https://leetcode.com/problems/basic-calculator-ii/description/
Quick Answer: This question evaluates skill in parsing and evaluating arithmetic expressions with integer operands and the operators +, -, *, and /, focusing on operator precedence and evaluation order within the Coding & Algorithms domain.
Given a string s representing a valid arithmetic expression containing non-negative integers, '+', '-', '*', '/', and spaces, compute its value. The expression contains no parentheses. Division between two integers should truncate toward zero. Return the evaluated integer result.
Constraints
- 1 <= len(s) <= 100000
- s contains only digits, '+', '-', '*', '/', and spaces
- The expression is valid and contains no parentheses
- Operands are non-negative integers (no unary plus/minus)
- Integer division truncates toward zero
- The final result fits in a 32-bit signed integer
Examples
Input: 3+2*2
Expected Output:
Input: 14 - 3*4 + 5 / 2
Expected Output:
Input: 3/2
Expected Output:
Input: 2-5*2
Expected Output:
Input: 0*10+5/2
Expected Output:
Input: 42
Expected Output:
Solution
def evaluate_expression(s: str) -> int:
total = 0
last = 0
num = 0
op = '+' # previous operator
for ch in s + '+': # sentinel to flush the last number
if ch == ' ':
continue
if ch.isdigit():
num = num * 10 + (ord(ch) - ord('0'))
elif ch in '+-*/':
if op == '+':
total += last
last = num
elif op == '-':
total += last
last = -num
elif op == '*':
last = last * num
elif op == '/':
# Truncate toward zero
last = int(last / num)
op = ch
num = 0
return total + last
Explanation
Perform a single left-to-right scan, maintaining: (1) total: sum of fully-resolved terms; (2) last: the most recent term not yet added to total; (3) num: the current number being parsed; (4) op: the previous operator. On encountering an operator (or at the end via a sentinel), apply the previous operator to 'last' and 'num'. For +/-, move the previous 'last' into 'total' and reset 'last' to +/-num. For */ apply the operation directly to 'last' to respect precedence. Finally, return total + last. Use int(a / b) to truncate toward zero for division.
Time complexity: O(n). Space complexity: O(1).
Hints
- Scan the string once while tracking the current number and the previous operator.
- Use a 'last term' variable to handle * and / precedence without a stack.
- Apply the previous operator when you meet a new operator or reach the end.
- To truncate toward zero in Python, use int(a / b) for division.