Java：通过布尔表达式查询HashMap中关键词对应的文档集合

Alright, let's break down how to solve this problem—you've got a term-to-documents HashMap, and you need to evaluate boolean expressions (with AND/OR/NOT) to get the matching documents. Here's a practical, hands-on approach:

First, map each boolean operator to a standard set operation—this simplifies the problem drastically:

• AND → Intersection: Documents present in both term's lists
• OR → Union: All documents from either term's list (no duplicates)
• NOT → Complement: All documents not in the term's list (requires knowing the full set of all documents first)

Let's use Python for the example (the logic translates easily to other languages like Java/C#):

1. Define Your Term-Document Map & Full Document Set #

First, set up your data and extract all unique documents (critical for NOT operations):

# Your term-to-documents HashMap (Python dict of sets for easy set operations)
term_docs = {
    "afternoon": {"Doc2"},
    "activities": {"Doc1", "Doc2", "Doc3"},
    "admissions": {"Doc1", "Doc2", "Doc4", "Doc5"},
    "alternate": {"Doc5"}
}

# Get the full set of all documents across all terms
all_docs = set()
for docs in term_docs.values():
    all_docs.update(docs)

2. Build an Expression Evaluator #

We'll write a function that parses the boolean expression, handles operator precedence (NOT > AND > OR), and computes the result using set operations:

def evaluate_boolean_expr(expr, term_docs, all_docs):
    # First handle nested parentheses by recursively evaluating inner expressions
    while '(' in expr:
        start_idx = expr.rfind('(')
        end_idx = expr.find(')', start_idx)
        sub_expr = expr[start_idx+1:end_idx]
        sub_result = evaluate_boolean_expr(sub_expr, term_docs, all_docs)
        # Replace the sub-expression with its result (marked as a set)
        expr = expr[:start_idx] + f"SET({sub_result})" + expr[end_idx+1:]
    
    # Step 1: Evaluate NOT operations (highest precedence)
    tokens = expr.split()
    i = 0
    while i < len(tokens):
        if tokens[i] == 'NOT':
            target = tokens[i+1]
            # Resolve the target: either a term or a precomputed set
            if target.startswith('SET('):
                target_set = eval(target[4:-1])
            else:
                target_set = term_docs.get(target, set())  # Unknown term = empty set
            # Compute complement
            result_set = all_docs - target_set
            # Replace NOT + target with the result set
            tokens = tokens[:i] + [f"SET({result_set})"] + tokens[i+2:]
        else:
            i += 1
    
    # Step 2: Evaluate AND operations (middle precedence)
    i = 0
    while i < len(tokens) - 1:
        if tokens[i+1] == 'AND':
            # Resolve left and right operands
            left = eval(tokens[i][4:-1]) if tokens[i].startswith('SET(') else term_docs.get(tokens[i], set())
            right = eval(tokens[i+2][4:-1]) if tokens[i+2].startswith('SET(') else term_docs.get(tokens[i+2], set())
            # Compute intersection
            result_set = left & right
            tokens = tokens[:i] + [f"SET({result_set})"] + tokens[i+3:]
        else:
            i += 1
    
    # Step 3: Evaluate OR operations (lowest precedence)
    i = 0
    while i < len(tokens) - 1:
        if tokens[i+1] == 'OR':
            # Resolve left and right operands
            left = eval(tokens[i][4:-1]) if tokens[i].startswith('SET(') else term_docs.get(tokens[i], set())
            right = eval(tokens[i+2][4:-1]) if tokens[i+2].startswith('SET(') else term_docs.get(tokens[i+2], set())
            # Compute union
            result_set = left | right
            tokens = tokens[:i] + [f"SET({result_set})"] + tokens[i+3:]
        else:
            i += 1
    
    # Return the final result set
    return eval(tokens[0][4:-1]) if tokens[0].startswith('SET(') else term_docs.get(tokens[0], set())

3. Test the Evaluator with Your Examples #

Let's run through the test cases you provided:

# Test 1: (afternoon AND activities) OR alternate
expr1 = "(afternoon AND activities) OR alternate"
result1 = evaluate_boolean_expr(expr1, term_docs, all_docs)
print(f"Result for '{expr1}': {', '.join(sorted(result1))}")
# Output: Doc2, Doc5

# Test 2: (afternoon AND activities) OR (admissions AND alternate)
expr2 = "(afternoon AND activities) OR (admissions AND alternate)"
result2 = evaluate_boolean_expr(expr2, term_docs, all_docs)
print(f"Result for '{expr2}': {', '.join(sorted(result2))}")
# Output: Doc2, Doc5

# Test 3: activities AND NOT afternoon
expr3 = "activities AND NOT afternoon"
result3 = evaluate_boolean_expr(expr3, term_docs, all_docs)
print(f"Result for '{expr3}': {', '.join(sorted(result3))}")
# Output: Doc1, Doc3

• Expression Format: The function expects spaces between all elements (e.g., afternoon AND activities, not afternoonANDactivities). If your input expressions don't have spaces, add a pre-processing step to split terms and operators.
• Unknown Terms: Any term not present in your HashMap is treated as an empty document set—so NOT unknown_term will return all documents.
• Precedence: The function respects standard boolean precedence: NOT is evaluated first, then AND, then OR. Parentheses override this order, as expected.

内容的提问来源于stack exchange，提问作者Shreyas SG