Interpreter pattern in LLD - System Design Exercise

Design: Interpreter Pattern Implementation

In scope: Designing the interpreter pattern structure, expression parsing, evaluation, and extensibility. Out of scope: Complex language parsing, error recovery, or integration with external systems.

Functional Requirements

FR1: Design a system that can interpret and evaluate simple expressions.

FR2: Support basic operations like addition, subtraction, multiplication, and division.

FR3: Allow easy extension to add new operations or expression types.

FR4: Provide a way to parse input strings into expression trees.

FR5: Evaluate expressions to produce a numeric result.

Non-Functional Requirements

NFR1: The system should handle expressions with up to 100 operations efficiently.

NFR2: Evaluation latency should be under 50ms for typical expressions.

NFR3: The design should be modular to support future extensions without modifying existing code.

NFR4: Memory usage should be optimized for embedded or low-resource environments.

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

Key Components

Abstract Expression interface or class

Terminal Expressions for numbers or literals

Non-terminal Expressions for operations (add, subtract, etc.)

Parser component to convert input strings into expression trees

Context or environment if variables or state are needed

Design Patterns

Interpreter pattern for expression evaluation

Composite pattern to represent expression trees

Factory pattern for creating expression objects

Visitor pattern for extending operations without modifying expressions

Reference Architecture

Input String --> Parser --> Expression Tree (Composite of Terminal and Non-terminal Expressions) --> Interpreter (Evaluate) --> Result

Components

Expression Interface

Abstract class or interface

Defines the interpret method for all expressions

TerminalExpression

Class

Represents numeric literals; returns their value on interpret

NonTerminalExpression

Class

Represents operations like add, subtract; interprets by combining child expressions

Parser

Class

Parses input strings into expression trees composed of Expression objects

Request Flow

1. User inputs an expression string (e.g., "3 + 5 * 2")

2. Parser reads the string and builds an expression tree using Terminal and NonTerminal expressions

3. The root expression's interpret method is called

4. Interpret method recursively evaluates child expressions and applies operations

5. Final numeric result is returned to the user

Database Schema

Not applicable as this is an in-memory pattern implementation without persistent storage.

Scaling Discussion

Bottlenecks

Parsing complex or very large expressions may be slow or memory intensive

Adding many new operations could complicate the expression hierarchy

Evaluation of deeply nested expressions may cause stack overflow or performance issues

Solutions

Optimize parser with iterative parsing or tokenization to reduce memory use

Use the Visitor pattern to add new operations without modifying existing expression classes

Implement tail-recursion optimization or iterative evaluation to handle deep expression trees

Interview Tips

Time: Spend 10 minutes explaining the problem and clarifying requirements, 20 minutes designing the expression classes and parser, 10 minutes discussing extensibility and scaling.

Explain how the Interpreter pattern models grammar rules as classes

Show how the Composite pattern helps represent nested expressions

Discuss how the parser converts strings into expression trees

Highlight extensibility by adding new expression types without changing existing code

Mention performance considerations for parsing and evaluation