Katkat
Back

Evaluate an arithmetic expression

DockerSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests the ability to parse and evaluate arithmetic expressions involving addition, subtraction, multiplication, and division, requiring careful handling of operator precedence and parsing multi-digit integers.

Problem: Evaluate Arithmetic Expression

Given a string s representing a non-negative arithmetic expression, implement a function to calculate the result. The expression contains integers, operators (+, -, *, /), and spaces. Integer division should truncate toward zero.

You cannot use built-in functions like eval().

Function Signature

def calculate(s: str) -> int:

Constraints

  • 1 <= len(s) <= 3 * 10^5
  • s consists of integers, operators, and spaces.
  • All intermediate results will fit in a 32-bit signed integer.

Examples

Example 1: Input: s = "3+2*2" Output: 7 Explanation: The multiplication 2*2 is performed first, followed by 3+4.

Example 2: Input: s = " 3/2 " Output: 1 Explanation: Division truncates toward zero.

Example 3: Input: s = " 3+5 / 2 " Output: 5

Edge Cases

  • Expressions with leading/trailing spaces.
  • Single integer inputs (e.g., "42").
  • Expressions where division results in negative numbers (e.g., "1 - 5 / 2").

Hints

Hint 1

Use a stack to store the results of operations that are not yet ready to be summed.

Hint 2

Treat multiplication and division as having higher precedence by calculating them immediately when the operator is encountered and storing the result on the stack.

Hint 3

Handle subtraction by pushing the negative of the number onto the stack and addition by pushing the positive, then sum the stack at the end.

Follow-up questions

  • How would you modify your solution to support parentheses (e.g., "(1+2)*3")?
  • What changes would be necessary to support floating-point numbers instead of integers?
  • Can you solve this with O(1) extra space, assuming the expression only contains '+' and '-'?