LOW-LEVEL DESIGN · BEHAVIORAL PATTERNS · BEHAVIORAL · 44 OF 48

Interpreter Design Pattern in Java: Build a Discount Rule Language

How the Interpreter pattern turns a small grammar into classes and evaluates an expression tree, using a tiny discount rule language of our own: terminal and non-terminal expressions, a context with cart values, a small parser that builds the tree, when a hand-written interpreter is right and when to use a library instead, and how it relates to Composite and Visitor.

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
  43. 43
  44. 44
  45. 45
  46. 46
  47. 47
  48. 48
1 / 17

Press play to hear the narration, or step through at your own pace. The Java example is below.

Java example

One file, Java 17, 211 lines, with a small main() demo. Save it as DiscountRuleInterpreter.java, then run javac DiscountRuleInterpreter.java && java DiscountRuleInterpreter.

import java.util.ArrayList;
import java.util.List;
import java.util.Map;

/** Interpreter: discount rules written as text, parsed into a tree of objects, evaluated per cart. */
public class DiscountRuleInterpreter {

    // ---------- 1. The problem: every rule is hard-coded ----------
    static int hardCodedDiscount(long total, long items, boolean firstOrder) {
        if (total >= 1500 && items >= 3) {
            return 10;
        }
        if (firstOrder || total >= 5000) {
            return 15;
        }
        return 0; // a new campaign means a new if and a new deploy
    }

    public static void main(String[] args) {
        System.out.println("Hard-coded: " + hardCodedDiscount(1800, 3, false) + "% off");

        // ---------- 2. A tree built by hand: items >= 3 and total >= 1500 ----------
        Condition byHand = new AndRule(new Compare("items", Op.GE, 3), new Compare("total", Op.GE, 1500));
        CartFacts cart = new CartFacts(Map.of("total", 1800L, "items", 3L, "firstOrder", 0L));
        System.out.println("Tree " + byHand.show() + " -> " + byHand.test(cart));

        // ---------- 3. Rules as data: parse once, evaluate for every cart ----------
        List<Promotion> promos = new ArrayList<>();
        promos.add(new Promotion("BUNDLE10", RuleParser.parse("items >= 3 and total >= 1500"), 10));
        promos.add(new Promotion("WELCOME15", RuleParser.parse("firstOrder == 1 or total >= 5000"), 15));
        promos.add(new Promotion("SMALL5", RuleParser.parse("not items < 2 and total >= 800"), 5));
        for (Promotion p : promos) {
            System.out.println(p.code() + " parsed as " + p.rule().show());
        }

        CartFacts newShopper = new CartFacts(Map.of("total", 900L, "items", 2L, "firstOrder", 1L));
        System.out.println("Cart A best promo: " + best(promos, cart));
        System.out.println("Cart B best promo: " + best(promos, newShopper));

        // ---------- 4. Bad rules fail when they are saved, not at checkout ----------
        try {
            RuleParser.parse("total => 100");
        } catch (IllegalArgumentException e) {
            System.out.println("Rejected rule: " + e.getMessage());
        }
    }

    static String best(List<Promotion> promos, CartFacts facts) {
        Promotion winner = null;
        for (Promotion p : promos) {
            if (p.rule().test(facts) && (winner == null || p.percentOff() > winner.percentOff())) {
                winner = p;
            }
        }
        return winner == null ? "none" : winner.code() + " (" + winner.percentOff() + "% off)";
    }
}

// ---------- The context: values for one evaluation ----------
record CartFacts(Map<String, Long> values) {
    long get(String name) {
        Long v = values.get(name);
        if (v == null) {
            throw new IllegalArgumentException("unknown field " + name);
        }
        return v;
    }
}

record Promotion(String code, Condition rule, int percentOff) { }

// ---------- The abstract expression ----------
interface Condition {
    boolean test(CartFacts facts);

    String show();
}

enum Op {
    GE(">="), LE("<="), GT(">"), LT("<"), EQ("==");

    final String symbol;

    Op(String symbol) {
        this.symbol = symbol;
    }

    boolean apply(long left, long right) {
        return switch (this) {
            case GE -> left >= right;
            case LE -> left <= right;
            case GT -> left > right;
            case LT -> left < right;
            case EQ -> left == right;
        };
    }

    static Op from(String text) {
        for (Op op : values()) {
            if (op.symbol.equals(text)) {
                return op;
            }
        }
        throw new IllegalArgumentException("unknown operator '" + text + "'");
    }
}

// ---------- Terminal expression: a leaf ----------
record Compare(String field, Op op, long value) implements Condition {
    @Override
    public boolean test(CartFacts facts) {
        return op.apply(facts.get(field), value);
    }

    @Override
    public String show() {
        return field + " " + op.symbol + " " + value;
    }
}

// ---------- Non-terminal expressions: combine children ----------
record AndRule(Condition left, Condition right) implements Condition {
    @Override
    public boolean test(CartFacts facts) {
        return left.test(facts) && right.test(facts);
    }

    @Override
    public String show() {
        return "(" + left.show() + " AND " + right.show() + ")";
    }
}

record OrRule(Condition left, Condition right) implements Condition {
    @Override
    public boolean test(CartFacts facts) {
        return left.test(facts) || right.test(facts);
    }

    @Override
    public String show() {
        return "(" + left.show() + " OR " + right.show() + ")";
    }
}

record NotRule(Condition inner) implements Condition {
    @Override
    public boolean test(CartFacts facts) {
        return !inner.test(facts);
    }

    @Override
    public String show() {
        return "NOT " + inner.show();
    }
}

/** Recursive descent: one method per grammar line. Tokens are separated by spaces. */
final class RuleParser {
    private final String[] tokens;
    private int pos;

    private RuleParser(String text) {
        this.tokens = text.trim().split("\\s+");
    }

    static Condition parse(String text) {
        RuleParser p = new RuleParser(text);
        Condition rule = p.orExpr();
        if (p.pos != p.tokens.length) {
            throw new IllegalArgumentException("unexpected '" + p.tokens[p.pos] + "'");
        }
        return rule;
    }

    private Condition orExpr() {
        Condition left = andExpr();
        while (peek("or")) {
            pos++;
            left = new OrRule(left, andExpr());
        }
        return left;
    }

    private Condition andExpr() {
        Condition left = unary();
        while (peek("and")) {
            pos++;
            left = new AndRule(left, unary());
        }
        return left;
    }

    private Condition unary() {
        if (peek("not")) {
            pos++;
            return new NotRule(unary());
        }
        if (pos + 3 > tokens.length) {
            throw new IllegalArgumentException("incomplete comparison");
        }
        String field = tokens[pos++];
        Op op = Op.from(tokens[pos++]);
        long value = Long.parseLong(tokens[pos++]);
        return new Compare(field, op, value);
    }

    private boolean peek(String word) {
        return pos < tokens.length && tokens[pos].equals(word);
    }
}

Notes

The problem

Here is how it usually starts. A discount method with a growing list of if statements. Total at least fifteen hundred and at least three items gives ten percent. First order, or a big cart, gives fifteen. Every change is a code edit, a review and a deploy, and the method keeps getting longer. The rules are really data that changes often, trapped inside code that should change rarely.

Hard-coded rules
int discount(Cart c) {
  if (c.total() >= 1500 && c.items() >= 3)
    return 10;
  if (c.firstOrder() || c.total() >= 5000)
    return 15;
  // next week: another if, another deploy
  return 0;
}

The idea

The idea: define a small grammar for your rules, make one class for each grammar rule, turn a sentence into a tree of those objects, then ask the root of the tree to evaluate itself. The formal version: Interpreter represents a grammar as a class hierarchy, and interprets sentences by walking an expression tree with a shared context. A rule like items at least three and total at least fifteen hundred becomes a tiny tree.

Interpreter in one line
  • define a small grammar,
  • make one class per rule of
  • the grammar, build a tree
  • from a sentence, and ask
  • the root to evaluate itself
  • rule text:
  • "items >= 3 and total >= 1500"

The grammar

Here is the whole grammar, just four lines. A rule is one or more and expressions joined by the word or. An and expression is one or more unary parts joined by and. A unary part is either not followed by another unary part, or a comparison. A comparison is a field name, an operator and a number. Because and sits lower in the grammar, it binds tighter than or, just like in Java.

Our rule grammar
rule    := andExpr ( "or" andExpr )*
andExpr := unary ( "and" unary )*
unary   := "not" unary | compare
compare := FIELD OP NUMBER

FIELD: total, items, firstOrder
OP:    >=  <=  >  <  ==

and binds tighter than or

Structure

Each grammar rule maps to a class, and all of them implement one Condition interface with a test method. Compare is a terminal expression, a leaf of the tree, because it holds no other conditions. AndRule, OrRule and NotRule are non-terminal expressions: they hold child conditions and combine their answers. Notice this is the Composite pattern underneath. Interpreter is Composite with a grammar on top.

Code: terminal

The Condition interface has one method, test, which takes the context. Compare is a record holding a field name, an operator and a number. Its test method reads the field from the context and applies the operator. The operator is an enum, so only the five known comparisons can exist. There is no string evaluation and no scripting engine. That matters for safety, since rule text may come from a web form.

Terminal expression
interface Condition {
  boolean test(CartFacts facts);
}
record Compare(String field, Op op,
               long value)
    implements Condition {
  public boolean test(CartFacts f) {
    return op.apply(f.get(field), value);
  }
}

Code: non-terminals

The non-terminals are just as small. AndRule holds a left and a right condition and returns true only when both are true. OrRule returns true when either is. NotRule flips its one child. They do not care whether a child is a leaf or another big subtree. Java's own short circuit rules apply too: if the left side of an and is false, the right side is never evaluated.

Non-terminal expressions
record AndRule(Condition l, Condition r)
    implements Condition {
  public boolean test(CartFacts f) {
    return l.test(f) && r.test(f);
  }
}

OrRule:  l.test(f) || r.test(f)
NotRule: !inner.test(f)

The context

The context is the input for one evaluation. Here it is CartFacts, a map from field names to numbers: total, number of items, and first order as one or zero. The tree is built once and reused, while a fresh context comes with every cart. Asking for an unknown field throws a clear error. That keeps a typo in a rule from quietly evaluating to zero and giving everyone a discount.

CartFacts
record CartFacts(Map<String, Long> v) {
  long get(String name) {
    Long x = v.get(name);
    if (x == null) throw new
      IllegalArgumentException(
        "unknown field " + name);
    return x;
  }
}

Building the tree

Who builds the tree? Strictly, parsing is not part of the pattern, but you need it. With a grammar this small, a recursive descent parser is enough: one method per grammar line. The or method reads an and expression, then while the next word is or, it reads another and wraps both in an OrRule. The other methods follow the same shape. Each rule is parsed once when marketing saves it, so a bad rule is rejected at save time, not at checkout.

RuleParser
Condition orExpr() {
  Condition left = andExpr();
  while (peek("or")) {
    pos++;
    left = new OrRule(left, andExpr());
  }
  return left;
}
// andExpr, unary, compare: same shape

A run-through

Let us run one cart through it. The engine calls test on the root, an OrRule. The OrRule asks its left child, an AndRule. The AndRule asks its first comparison, which reads items from the cart facts: three, which is at least three, so true. The second comparison checks the total, also true. The AndRule returns true, so the OrRule can stop without asking its right side. The promotion applies.

Using it

Now promotions are data. Each one is a rule string and a percentage, stored in a table and edited from an admin screen. On startup, or when a rule is saved, the engine parses it once. At checkout it tests every promotion against the cart facts and picks the best match. Adding a campaign is now a row, not a release, and the code you test stays the same.

Rules as data
  • "items >= 3 and total >= 1500"
  • -> 10% off
  • "firstOrder == 1 or
  • total >= 5000" -> 15% off
  • "not items < 2 and
  • total >= 800" -> 5% off
  • parse once, store the tree,
  • test every cart, best wins

When to use it

Use Interpreter when the language is small, the rules change more often than the code, and you want users to have limited, safe power. Skip it when the grammar is large or keeps growing: one class per rule becomes hard to manage, and a parser generator or an existing expression library is better. Walking a tree of objects is also slower than compiled code, which matters only on very hot paths.

Use it / skip it
  • use it when:
  • • the language is small
  • • rules change more than code
  • • you need safe, limited power
  • skip it when:
  • • grammar is large or growing
  • • speed is critical: compile
  • instead of walking a tree
  • • a library already fits

Safety

A word on safety. Rule text often comes from a form, so treat it as untrusted. Our design only allows known fields and five operators, so a rule cannot call a method or read a file. Validate rules when they are saved, cap their length and nesting depth, and never hand rule text to a general script engine. A tiny language you control is much safer than a full one you do not.

Keep it safe
  • • whitelist the fields
  • • enum for operators
  • • validate when the rule is
  • saved, not at checkout
  • • limit rule length and depth
  • • never pass rule text to a
  • script engine or eval

Where you see it

You meet this idea often. Java's regex Pattern class compiles a regular expression into an internal tree of node objects and then runs that tree against your text. Expression languages in popular frameworks parse a string into a tree of nodes and evaluate it against a context. Feature flag targeting, alert rules and search filters all follow the same plan: small grammar, tree of objects, evaluate with a context.

In real code
  • java.util.regex.Pattern:
  • compiles a regex into an
  • internal tree of match nodes
  • expression languages in
  • frameworks parse text into
  • node trees they evaluate
  • search filters, feature flag
  • targeting, alert rules

Related patterns

How does it relate to its neighbours? Composite is the shape: a tree where groups and leaves share one interface. Interpreter is a Composite whose nodes follow a grammar and know how to evaluate themselves. If you later need many operations on the same tree, like pretty printing, optimising or validating, you add a Visitor rather than a new method on every node class.

How it differs
  • Composite: a tree where a
  • group and a leaf share
  • one interface
  • Interpreter: a Composite
  • whose nodes follow a grammar
  • and evaluate themselves
  • Visitor: add print, optimise
  • or check to the same tree

In LLD interviews

In interviews this fits coupon and discount engines, access rules based on role and time, alert conditions in a monitoring tool, and workflow conditions. Common mistakes are evaluating user text as code, skipping validation until checkout, and writing one giant class that switches on token types instead of one small class per grammar rule. Keep the grammar tiny and say why.

Where it fits
  • coupon and discount engine
  • access rules: role and time
  • alerting: cpu > 90 for 5m
  • workflow conditions
  • common mistakes:
  • • eval() on user text
  • • no validation at save time
  • • one giant class with a
  • switch on token type

Interview questions

What is the Interpreter pattern?

It represents a small language as a class hierarchy, one class per grammar rule. A sentence is parsed into a tree of these objects, and calling evaluate on the root walks the tree using a shared context to produce the result.

What are terminal and non-terminal expressions?

Terminal expressions are leaves that hold no child expressions, such as a number, a variable or a single comparison. Non-terminal expressions, such as and, or and not, hold child expressions and combine their results.

What is the context in the Interpreter pattern?

It is the input for one evaluation, such as the values of variables or cart fields. The tree stays the same and is reused, while a new context is passed in for each evaluation.

Is parsing part of the Interpreter pattern?

Not strictly. The pattern describes how to represent and evaluate the tree. You still need something to build the tree, usually a small recursive descent parser for tiny grammars or a parser generator for larger ones.

When should you not use Interpreter?

When the grammar is large or changes often, since one class per rule becomes hard to maintain, or when performance is critical. In those cases use a parser generator, an existing expression library or compile rules into faster code.

How is Interpreter related to Composite?

The expression tree is a Composite: leaves and groups share one interface. Interpreter adds a grammar on top and gives each node the job of evaluating itself against a context.

How would you design a rule engine for discounts?

Store each promotion as a rule string plus a benefit. Parse rules into an expression tree when they are saved, rejecting invalid ones. At checkout, build a context from the cart, evaluate each tree and apply the best matching promotion.

How do you keep a user-written rule language secure?

Allow only known fields and a fixed set of operators, validate rules when they are saved, limit length and nesting depth, and never pass rule text to a general script engine. The interpreter should be unable to do anything except compare values.