পার্স ট্রি ও অ্যাম্বিগুইটি

# পার্স ট্রি = (label, children) নেস্টেড টাপল -- children ফাঁকা মানে leaf
# len(children)==1 মানে পাস-থ্রু নন-টার্মিনাল রুল (যেমন <expr>::=<term>)
# len(children)==3 মানে বাইনারি অপারেটর রুল (operand, operator-leaf, operand)

def evaluate_parse_tree(node):
    label, children = node
    if not children:
        return float(label)                        # সংখ্যা-লিফ
    if len(children) == 1:
        return evaluate_parse_tree(children[0])     # পাস-থ্রু নন-টার্মিনাল
    if len(children) == 3:
        left, op_node, right = children
        op = op_node[0]
        left_val = evaluate_parse_tree(left)
        right_val = evaluate_parse_tree(right)
        if op == '+': return left_val + right_val
        if op == '-': return left_val - right_val
        if op == '*': return left_val * right_val
        if op == '/': return left_val / right_val
    raise ValueError(f"অপ্রত্যাশিত নোড আকৃতি: {node}")

# --- নাইভ অ্যাম্বিগুয়াস গ্রামার: <expr> ::= <expr>+<expr> | <expr>*<expr> | number ---

tree_A = ('<expr>', [                                          # গ্রুপিং: (2 + 3) * 4
    ('<expr>', [('<expr>', [('2', [])]), ('+', []), ('<expr>', [('3', [])])]),
    ('*', []),
    ('<expr>', [('4', [])]),
])

tree_B = ('<expr>', [                                          # গ্রুপিং: 2 + (3 * 4)
    ('<expr>', [('2', [])]),
    ('+', []),
    ('<expr>', [('<expr>', [('3', [])]), ('*', []), ('<expr>', [('4', [])])]),
])

result_A = evaluate_parse_tree(tree_A)
result_B = evaluate_parse_tree(tree_B)

print('একই স্ট্রিং "2 + 3 * 4"-এর দুটি ভিন্ন পার্স ট্রি (নাইভ অ্যাম্বিগুয়াস গ্রামার):\n')
print(f"  Tree A -- (2 + 3) * 4  →  evaluate_parse_tree(tree_A) = {result_A}")
print(f"  Tree B -- 2 + (3 * 4)  →  evaluate_parse_tree(tree_B) = {result_B}")
print(f"\n  ফলাফল ভিন্ন কিনা: {result_A != result_B}  -- একই ইনপুট, একই গ্রামার, দুই রকম অর্থ!")

# --- L12-এর লেয়ার্ড আন-অ্যাম্বিগুয়াস গ্রামার: <expr>/<term>/<factor> ---
# এই গ্রামারে "2 + 3 * 4"-এর জন্য মাত্র ONE বৈধ পার্স ট্রি সম্ভব

tree_correct = ('<expr>', [
    ('<expr>', [('<term>', [('<factor>', [('2', [])])])]),
    ('+', []),
    ('<term>', [
        ('<term>', [('<factor>', [('3', [])])]),
        ('*', []),
        ('<factor>', [('4', [])]),
    ]),
])

result_correct = evaluate_parse_tree(tree_correct)
print(f"\nL12-এর লেয়ার্ড গ্রামার -- একমাত্র বৈধ পার্স ট্রি:")
print(f"  evaluate_parse_tree(tree_correct) = {result_correct}")
print(f"  স্ট্যান্ডার্ড precedence (multiply আগে) মিলছে কিনা: {result_correct == 14.0}")