Katkat
Back

Evaluate an Integer Arithmetic Expression with Parentheses

ByteDanceSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests the ability to evaluate arithmetic expressions containing addition, subtraction, multiplication, and division, while correctly handling parentheses, operator precedence, and unary operators without using recursion.

Problem Statement

Given a string expression representing a mathematical expression, implement a function calculate(expression) that evaluates the result. The expression contains non-negative integers, +, -, *, /, parentheses (), and unary - signs.

Rules:

  1. The expression follows standard operator precedence: parentheses first, followed by * and /, then + and -.
  2. Operations of the same precedence are evaluated left-to-right.
  3. Division a / b should truncate toward zero (e.g., -5 / 2 = -2).
  4. You may assume the input is always valid.
  5. Do not use built-in evaluation functions like eval().
  6. Your solution must be iterative to handle deeply nested expressions without hitting stack overflow limits.

Function Signature

def calculate(expression: str) -> int:
    pass

Examples

Example 1: Input: "3 + 2 * 2" Output: 7

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

Example 3: Input: "- (3 + 2)" Output: -5

Constraints

  • 1 <= expression.length <= 10^5
  • The expression consists of digits, +, -, *, /, (, ) and spaces.
  • All intermediate and final results fit in a 32-bit signed integer.

Hints

Hint 1

To handle precedence without recursion, use two stacks: one for numbers and one for operators.

Hint 2

When encountering a unary minus at the start of an expression or after an opening parenthesis, treat it as `0 - x`.

Hint 3

Process operators by checking their precedence against the top of the operator stack before pushing new operators.

Follow-up questions

  • How would you modify your solution to support exponentiation (`^`) with right-associativity?
  • What changes are needed to support floating-point numbers instead of integers?
  • How can you optimize the space complexity if the expression contains many nested parentheses?