Interpreter
Part of the free Low-Level Design course on LogicWiz, in the chapter: Behavioural patterns III. The class-diagram exercises run in the app.
The coupon rule that marketing wants to edit
"Marketing wants to write coupon rules themselves, like 'cart over 500 and a dairy item'. They do not want to wait for our release."
Priya, after a planning meeting
Rules that arrive as text
Today each SwiftKart coupon has its eligibility written in Java: cart.total() > 500 && cart.hasCategory("DAIRY"). Marketing runs dozens of offers a month. Each change needs a code change, a review and a release.
Product has a better idea. Store each rule as text in the coupon table, so marketing can edit it on an admin page: cartTotal > 500 AND category = DAIRY. The program must read that text and answer yes or no for a cart.
Arjun started with the quickest reader he could think of. He split the text at the spaces and took three words: a field, an operator and a number.
static boolean eligible(String rule, Map<String, Long> numbers) {
String[] t = rule.split(" "); // field, operator, value
long left = numbers.get(t[0]);
long right = Long.parseLong(t[2]);
return t[1].equals(">") ? left > right : left < right;
}
He tried the rule above on a cart worth 640 rupees that has only snacks in it. The right answer is no, because there is no dairy item.
Map<String, Long> numbers = Map.of("cartTotal", 640L); // the cart has only SNACKS in it
String rule = "cartTotal > 500 AND category = DAIRY";
System.out.println("eligible: " + eligible(rule, numbers));
eligible: true
The answer is yes. The code reads cartTotal > 500, and it ignores every word after the third, including AND category = DAIRY. A customer with no dairy gets the dairy coupon, and SwiftKart pays for it. This reader fails because it does not see the structure of the text. AND is not a fourth word in a list. It joins two conditions. A rule can also contain OR and brackets, so a rule is a small language with its own structure, and we need a proper way to read it.
A small language, a grammar and a tree
Think of a cashier who gets a handwritten note: "10 percent off if the bill is over 500 and the customer has a card". She does not read it as one long sentence. She breaks it into small conditions, checks each one against the bill, and combines the answers with "and" or "or".
Where the picture stops working: a person guesses what a smudged note means. A program must not guess. Arjun's bug was a guess. A reader of rules should refuse text it does not understand and say where the problem is.
First we write down exactly which sentences are allowed. A grammar is a list of rules that says which sentences belong to a language. Here is the grammar for our rules:
rule : andPart ( "OR" andPart )*
andPart : primary ( "AND" primary )*
primary : "(" rule ")" or comparison
comparison : field operator value
Read it in words. A rule is one or more andParts joined by OR. The ( ... )* means the group in brackets may repeat zero or more times. An andPart is one or more primary items joined by AND. A primary is either a rule inside brackets or a single comparison. A comparison is a field, an operator (>, < or =) and a value.
This grammar also fixes the order of work. AND sits lower in the list than OR, so AND joins first. This is like multiplication before addition in 2 + 3 * 4. The brackets let marketing change the order.
Next, we turn each sentence into a tree of small objects. Here is cartTotal > 500 AND category = DAIRY:
flowchart TD
A["AND"] --> B["cartTotal > 500"]
A --> C["category = DAIRY"]
This is an abstract syntax tree, or AST. The spaces and brackets of the text are gone. Only the meaning is left. The leaves are comparisons. The inner nodes combine the answers of their children. To get the answer, you ask the root. The root asks its children, and so on down. A tree like this is a Composite, which you met in the bundle lesson.
This is the Interpreter pattern: you represent each rule of a small language as a class, and a sentence of the language as a tree of objects. To evaluate the sentence, you ask the root to evaluate itself against a context, the facts the rule is checked against, such as the cart total and its categories. The roles are:
- Expression: the interface, with one method
evaluate(context). - Terminal expression: a leaf that answers directly.
CompareandHasare terminals. - Nonterminal expression: a node that holds other expressions and combines their answers.
AndandOrare nonterminals. - Context: the cart's facts.
- Parser: the code that turns text into the tree. The classic pattern leaves it out, but you need it.
classDiagram
class Expr {
<<interface>>
+evaluate(c: Context) boolean
}
Expr <|.. Compare
Expr <|.. Has
Expr <|.. And
Expr <|.. Or
And o-- Expr : left and right
Or o-- Expr : left and right
Expr ..> Context
RuleParser ..> Expr : builds
Build it step by step
Step 1: the context and the leaves. The context holds numbers and sets of words. A cart has one total but many categories, so category = DAIRY means "some item is in DAIRY".
public final class Context {
private final Map<String, Long> numbers;
private final Map<String, Set<String>> words;
public Context(Map<String, Long> numbers, Map<String, Set<String>> words) {
this.numbers = numbers;
this.words = words;
}
public long number(String field) {
Long value = numbers.get(field);
if (value == null) throw new IllegalArgumentException("Unknown number field: " + field);
return value;
}
public boolean has(String field, String word) {
return words.getOrDefault(field, Set.of()).contains(word);
}
}
Compare handles cartTotal > 500. Has handles category = DAIRY.
public interface Expr {
boolean evaluate(Context context);
}
record Compare(String field, String op, long value) implements Expr {
public boolean evaluate(Context context) {
long actual = context.number(field);
return switch (op) {
case ">" -> actual > value;
case "<" -> actual < value;
default -> actual == value;
};
}
}
record Has(String field, String word) implements Expr {
public boolean evaluate(Context context) { return context.has(field, word); }
}
Step 2: the inner nodes. Each one asks its two children. This is the recursion.
record And(Expr left, Expr right) implements Expr {
public boolean evaluate(Context context) {
return left.evaluate(context) && right.evaluate(context);
}
}
record Or(Expr left, Expr right) implements Expr {
public boolean evaluate(Context context) {
return left.evaluate(context) || right.evaluate(context);
}
}
The tree for our rule can now be built by hand, with no parser:
static Expr byHand() {
return new And(new Compare("cartTotal", ">", 500), new Has("category", "DAIRY"));
}
Step 3: the parser. It turns text into that tree. This is a recursive descent parser: one method for each line of the grammar, and each method calls the methods for the lines below it. All of these methods sit inside one class, RuleParser. First, the setup. It puts spaces around brackets and splits the text into words. accept takes the next word only if it matches.
private final List<String> tokens;
private int pos = 0;
private RuleParser(String text) {
String spaced = text.replace("(", " ( ").replace(")", " ) ").trim();
tokens = spaced.isEmpty() ? List.of() : List.of(spaced.split("\\s+"));
}
public static Expr parse(String text) {
RuleParser parser = new RuleParser(text);
Expr rule = parser.orRule();
if (parser.pos < parser.tokens.size()) throw parser.error("unexpected '" + parser.tokens.get(parser.pos) + "'");
return rule;
}
private boolean accept(String token) { // consume the next token only if it matches
if (pos < tokens.size() && tokens.get(pos).equals(token)) { pos++; return true; }
return false;
}
private void expect(String token) {
if (!accept(token)) throw error("expected '" + token + "'");
}
Now the grammar lines that join things. The code looks like the grammar, with andPart named andRule in code:
private Expr orRule() {
Expr left = andPart();
while (accept("OR")) left = new Or(left, andPart());
return left;
}
private Expr andPart() {
Expr left = primary();
while (accept("AND")) left = new And(left, primary());
return left;
}
private Expr primary() {
if (accept("(")) {
Expr inner = orRule(); // the rule calls itself: this is the recursion
expect(")");
return inner;
}
return comparison();
}
orRule calls andPart first, so AND groups tighter than OR. primary calls orRule again for brackets. A method that calls itself through other methods is the recursion that lets rules nest to any depth.
Last, the comparison. It checks each word and refuses what it does not understand:
private Expr comparison() {
String field = word("a field name");
String op = word("an operator: >, < or =");
String value = word("a value");
if (!List.of(">", "<", "=").contains(op)) throw error("unknown operator '" + op + "'");
if (value.matches("\\d+")) return new Compare(field, op, Long.parseLong(value));
if (!op.equals("=")) throw error("a word can only be compared with =");
return new Has(field, value);
}
private String word(String what) {
if (pos >= tokens.size()) throw error("expected " + what + " but the rule ended");
String token = tokens.get(pos);
if (List.of("AND", "OR", "(", ")").contains(token)) throw error("expected " + what + " but found '" + token + "'");
pos++;
return token;
}
private IllegalArgumentException error(String message) {
return new IllegalArgumentException("Rule error near word " + (pos + 1) + ": " + message);
}
Step 4: run it. A small helper, cart(total, categories...), builds a context. Our rule is true for 640 rupees with dairy and snacks, false for snacks only, and false for 300 rupees with dairy:
Expr rule = RuleParser.parse("cartTotal > 500 AND category = DAIRY");
System.out.println(rule);
System.out.println(rule.evaluate(cart(640, "DAIRY", "SNACKS")));
System.out.println(rule.evaluate(cart(640, "SNACKS")));
System.out.println(rule.evaluate(cart(300, "DAIRY")));
And[left=Compare[field=cartTotal, op=>, value=500], right=Has[field=category, word=DAIRY]]
true
false
false
The first line is the tree, as Java prints the nodes. The order of work matters. The next cart has 300 rupees and a bakery item. Without brackets, the rule is "(total over 500 and dairy) or bakery", which is true. With brackets around the two categories, it is false:
Expr loose = RuleParser.parse("cartTotal > 500 AND category = DAIRY OR category = BAKERY");
Expr tight = RuleParser.parse("cartTotal > 500 AND (category = DAIRY OR category = BAKERY)");
Context small = cart(300, "BAKERY");
System.out.println(loose.evaluate(small));
System.out.println(tight.evaluate(small));
true
false
Bad text gets a clear error, not a guess. These four rules are cartTotal >, cartTotal > 500 AND, category > DAIRY and cartTotal > 500 ):
Rule error near word 3: expected a value but the rule ended
Rule error near word 5: expected a field name but the rule ended
Rule error near word 4: a word can only be compared with =
Rule error near word 4: unexpected ')'
Parse the text when marketing saves the rule, so a mistake shows on the admin page, not at a customer's checkout. Keep the tree and reuse it for every cart. Parsing again for each cart repeats the same work.
Interpreter, a lookup table, or Strategy?
Most rule problems do not need a language. Ask three questions in this order.
Does every rule have the same shape? If every coupon has a minimum total and one category, use a table with two columns and a row for each coupon. Marketing fills in a form. This is the cheapest answer:
record CouponRow(String code, long minTotal, String category) {
boolean eligible(long cartTotal, Set<String> categories) {
return cartTotal > minTotal && categories.contains(category);
}
}
Do developers write the rules in Java? Then build the tree in code, as we did by hand above, and skip the parser. Or give each rule its own class, the Strategy way, with MinTotalRule and CategoryRule combined by an AllOf class. Strategy picks one interchangeable way to do a job. It does not combine rules from text.
Do rules arrive as text, combine freely and change without a release? Then use Interpreter, with the tree and a parser.
The costs are real. You now own a language. Each new operator means a grammar line, a node class and a parser change. You must write error messages and tests for bad text. Never run rule text as Java code. A parser that builds only your known node classes is what keeps marketing's text from doing anything else. When the grammar outgrows one screen of code, use an existing expression library instead of growing a hand-written parser.
In a mock round, a candidate said: "Interpreter is for any rule-based problem, so I will use it for the split types in the expense-sharing problem." The split types are three fixed choices: equal, exact and percent. That is Strategy, and there is no text to parse.
Be honest in interviews: most problems never need Interpreter. The parking lot, the elevator, the cache and the expense-sharing problem do not. Interpreter fits a rule engine for offers or fraud checks, a filter such as "price under 500 and brand is X", a calculator, and spreadsheet formulas. Even there, interviewers usually accept the tree of expression classes and treat the parser as extra.
Practice: turn a rule string into expression classes
The starter is Arjun's first service, with one method that takes the rule text and splits it. Add an expression interface with an evaluate method, four expression classes, and a parser that builds them.
📌 Summary: Interpreter turns text rules into a tree of small expression classes that evaluate themselves against a context. A parser builds the tree. Use a table or plain objects when rules are not text.
What Arjun learns next
Arjun now knows the behavioural patterns, and Priya asks him to explain the coupon flow to a new teammate. Words are slow. She shows him how to draw who calls whom, in time order. That is the sequence diagram.
Check your understanding
- Arjun's split-by-spaces reader says a snacks-only cart of 640 rupees is eligible for `cartTotal > 500 AND category = DAIRY`. What is the root cause?
- With the lesson's grammar, how is `A AND B OR C` read?
- A candidate wants Interpreter for the equal, exact and percent split types in an expense-sharing design. What is the best reply?
- Every coupon has a minimum cart total and one category, and nothing else. Marketing edits them on a form. What fits best?