如何判断仅含+或+/-运算符的两个数学表达式是否等价？

Hey there! I totally get why the expression tree approach felt stuck—comparing tree structures directly gets messy fast when dealing with commutative and associative properties like addition. Let’s break down simpler, more effective solutions for both parts of your interview question:

Part 1: Equivalence for Expressions with Only "+" Operators #

The key here leans on two core math rules: addition is commutative (order doesn’t matter) and associative (grouping with parentheses doesn’t matter). That means two expressions are equivalent if and only if they contain exactly the same terms (counting duplicates, if any) in any order or grouping.

How to Implement It #

You don’t need complex tree comparisons here—just strip out all parentheses, split the expression into individual terms, and check if the two sets of terms (accounting for frequency) are identical.

Example code in Python:

from collections import Counter

def are_add_equivalent(expr1: str, expr2: str) -> bool:
    # Helper to clean and split an expression into terms
    def get_terms(expr):
        # Remove all parentheses, split by "+", and clean up whitespace
        raw_terms = expr.replace("(", "").replace(")", "").split("+")
        return [term.strip() for term in raw_terms if term.strip()]
    
    terms1 = get_terms(expr1)
    terms2 = get_terms(expr2)
    
    # Compare term frequencies (handles duplicates like "A+A" vs "A+A")
    return Counter(terms1) == Counter(terms2)

This works for any valid "+"-only expression—whether it’s A+B+C vs (A+(B+C)) or 2A+B vs B+2A (treating "2A" as a single term).

Part 2: Equivalence for Expressions with "+" and "-" Operators #

Subtraction adds a twist, but we can simplify it by converting everything to signed terms: any subtraction can be rewritten as adding the negative of a term (e.g., A - B = A + (-B)). When parentheses are involved, a leading "-" flips the sign of every term inside the parentheses (e.g., A - (-B + C) = A + B - C).

How to Implement It #

We’ll parse each expression into a dictionary where keys are terms and values are their net coefficients (total sign/count). If the dictionaries match, the expressions are equivalent.

Here’s a robust parsing approach using a stack to handle nested parentheses:

from collections import Counter

def parse_signed_terms(expr: str) -> dict:
    term_counts = Counter()
    stack = [1]  # Tracks the cumulative sign multiplier for the current context
    current_sign = 1
    i = 0
    n = len(expr)
    
    while i < n:
        char = expr[i]
        if char in "+-":
            current_sign = 1 if char == "+" else -1
            i += 1
        elif char == "(":
            # Push the current cumulative sign to the stack
            stack.append(current_sign * stack[-1])
            current_sign = 1
            i += 1
        elif char == ")":
            # Pop the context sign when exiting parentheses
            stack.pop()
            i += 1
        elif char.isalnum():
            # Extract the full term (handles coefficients like "2A")
            j = i
            while j < n and expr[j].isalnum():
                j += 1
            term = expr[i:j]
            # Calculate the final sign for this term
            final_sign = current_sign * stack[-1]
            term_counts[term] += final_sign
            i = j
        else:
            # Skip whitespace or invalid characters (assuming valid input)
            i += 1
    
    # Remove terms with zero net coefficient (they cancel out)
    return {term: cnt for term, cnt in term_counts.items() if cnt != 0}

def are_add_sub_equivalent(expr1: str, expr2: str) -> bool:
    return parse_signed_terms(expr1) == parse_signed_terms(expr2)

Testing your example: A+B-C and A-(-B+C) both parse to {"A": 1, "B": 1, "C": -1}, so the function returns True.

What About Your Expression Tree Idea? #

If you still want to use expression trees, here’s how to adjust:

1. For "+"-only trees: Collect all leaf nodes (terms) and compare their frequency counts—ignore the internal "+" node structure entirely, since grouping doesn’t matter.
2. For "+"/"-" trees: Traverse the tree to convert all subtractions into additions of negative terms, then merge equivalent leaves (summing their signs/coefficients). Finally, compare the merged leaf sets between the two trees.

That said, the term-parsing approach is far more efficient and easier to implement correctly than tree comparisons here.

内容的提问来源于stack exchange，提问作者danish sodhi