Katkat
Back

Evaluate an arithmetic expression

InstacartSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question tests the ability to evaluate a mathematical string containing integers, addition, subtraction, multiplication, and division, requiring an understanding of operator precedence and the use of stacks.

Problem Statement

Given a string s that represents an arithmetic expression, implement a function to evaluate it. The expression contains non-negative integers, the operators +, -, *, /, and parentheses ( and ). The division operator performs integer division, truncating toward zero. You may assume that the input expression is always valid and does not contain spaces.

Function Signature

def calculate(s: str) -> int:

Constraints

  • 1 <= len(s) <= 10^5
  • s consists of digits, +, -, *, /, (, and ).
  • The result will fit in a 32-bit signed integer.

Examples

Example 1: Input: s = "3+2*2" Output: 7 Explanation: Multiplication happens before addition.

Example 2: Input: s = "(1+(4+5+2)-3)+(6+8)" Output: 23

Edge Cases

  • Expressions with nested parentheses.
  • Expressions with a single integer.
  • Division involving negative numbers (e.g., -3 / 2 should evaluate to -1).

Hints

Hint 1

Use two stacks: one for storing numbers and one for storing operators to manage precedence.

Hint 2

Alternatively, use a single stack to store values and process multiplication/division immediately while delaying addition and subtraction by changing the sign of the next number.

Hint 3

When encountering an opening parenthesis, recursively call the function or treat the sub-expression as a new calculation scope.

Follow-up questions

  • How would you modify your solution to handle floating-point numbers instead of integers?
  • How would you handle invalid input (e.g., unbalanced parentheses or division by zero)?
  • What is the time and space complexity of your approach, and can it be optimized further?