Katkat
Back

Design a String Calculator with Explicit Grammar and Evaluation Rules

MetaSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

This problem tests the ability to implement a parser for basic mathematical expressions, specifically focusing on handling operator precedence and parentheses using a stack-based approach.

Problem Statement

Design a function calculate(s: str) -> int that evaluates a string containing non-negative integers, '+', '-', '*', '/', and parentheses '()'. The expression will always be valid, and division should perform integer truncation toward zero.

Rules

  1. Integer operands can consist of multiple digits (e.g., "12 + 3").
  2. Multiplication and division have higher precedence than addition and subtraction.
  3. Parentheses are used to override default precedence.
  4. You may assume spaces exist between tokens or within numbers, but your parser should handle them gracefully.

Examples

Example 1: Input: "3 + 2 * 2" Output: 7 Explanation: Multiplication is performed first: 3 + (2 * 2) = 7.

Example 2: Input: "(3 + 5) / 2" Output: 4 Explanation: Parentheses are evaluated first: 8 / 2 = 4.

Constraints

  • Length of s is between 1 and 10,000.
  • Operands are non-negative integers.
  • Division by zero will not occur.
def calculate(s: str) -> int:
    pass

Hints

Hint 1

Consider using two stacks: one to keep track of numbers and another to keep track of operators.

Hint 2

When encountering a closing parenthesis, process the operators on the stack until an opening parenthesis is found.

Hint 3

Implement an operator precedence function to determine whether an operator on the stack should be executed before the current one.

Follow-up questions

  • How would you modify your solution to support negative unary operators (e.g., "-5 + 3")?
  • How would you extend the grammar to support exponentiation ('^')?
  • What are the time and space complexity trade-offs of using recursion versus an iterative stack-based approach?