Tree traversal আর expression tree — prefix, infix, postfix

১ · Ordered rooted tree আর universal address

প্রথমে কয়েকটি শব্দ ঝালিয়ে নিই; বিস্তারিত সংজ্ঞা আর প্রমাণ পর্ব ৬৫ “Tree — ধর্ম, rooted tree আর m-ary tree-এর হিসাব”-এ। একটি tree হলো cycle-হীন connected graph. একটি rooted tree-তে একটি vertex-কে root ধরা হয়, আর প্রতিটি edge-কে root থেকে দূরে যাওয়ার দিকে ভাবা হয়। তখন প্রতিটি অ-root vertex-এর ঠিক একজন parent; যাদের কোনো সন্তান নেই তারা পাতা (leaf), বাকিরা internal vertex. একটি vertex v আর তার সব বংশধর মিলে v-এর subtree. Root থেকে v পর্যন্ত path-এর দৈর্ঘ্য v-এর level, আর সবচেয়ে বড় level হলো গাছের height.

ক্রম থাকলে প্রতিটি vertex-কে একটি নিখুঁত ঠিকানা দেওয়া যায়।

ঠিকানাগুলো তুলনা করার নিয়ম হলো lexicographic order, যা অভিধানে শব্দ সাজানোর নিয়মের মতো (পর্ব ৫৬-এ সংজ্ঞা আর প্রমাণ যে এটি একটি total order). দুটি ঠিকানা x = a₁.⋯.a_m আর y = b₁.⋯.b_n-এর জন্য x < y যদি (ক) x হলো y-এর একটি প্রকৃত prefix (m < n আর প্রথম mটি সংখ্যা মেলে), অথবা (খ) প্রথম যে স্থানে i তারা আলাদা, সেখানে a_i < b_i. Root-এর খালি ঠিকানা সবার prefix, তাই সবার আগে। উদাহরণ: 1.2 < 2 (প্রথম সংখ্যা 1 < 2), 2.1 < 2.1.1 (prefix), 2.1.1 < 2.2 (দ্বিতীয় স্থানে 1 < 2). ছবির ৯টি ঠিকানা সাজালে পাই: 0, 1, 1.1, 1.2, 2, 2.1, 2.1.1, 2.2, 3.

২ · Preorder, inorder, postorder — তিনটি recursive সংজ্ঞা

একটি ordered rooted tree T-এর root r, আর তার সন্তানদের subtree ক্রমে T₁, T₂, …, T_k (k = 0 মানে T একটি একা পাতা)। তিনটি traversal-এর সংজ্ঞা পর্ব ১২-এর structural recursion: পাতার জন্য একটি নিয়ম, আর বড় গাছের জন্য ছোট subtree-গুলোর ফল জোড়া দেওয়ার নিয়ম।

মনে রাখার সহজ উপায়: নামের “pre”, “in”, “post” বলে root কখন আসে: আগে, মাঝে, শেষে। প্রতিটি subtree-র ভেতরেও একই নিয়ম আবার খাটে। গাছের বাইরের সীমানা ধরে বাঁ দিক থেকে ঘুরে আসার কথা ভাবুন: প্রতিটি vertex-এর পাশ দিয়ে প্রথমবার যাওয়ার সময় নাম লিখলে preorder, শেষবার পেরোনোর সময় লিখলে postorder. নিচের stepper ছবির বিভাগ-গাছে চারটি ক্রম ধাপে ধাপে দেখায়।

1সব: মুদি, গ্যাজেট, পোশাক2preorder(মুদি)3preorder(সব)4inorder(সব)5postorder(সব)6level order(সব)

চতুর্থ ক্রমটি depth-first নয়, “breadth-first”: level order আগে কাছের সবাইকে দেখে, তারপর দূরের। এটি rooted tree-তে BFS-এর একটি বিশেষ রূপ, আর এর স্বাভাবিক সঙ্গী একটি queue (লাইন: যে আগে ঢোকে, সে আগে বের হয়)। Root-কে queue-তে রাখুন; তারপর বারবার সামনের vertex বের করে লিখুন আর তার সন্তানদের ক্রমে পেছনে যোগ করুন। Queue-তে সবসময় একটি level-এর শেষ অংশ আর পরের level-এর শুরু থাকে, এই invariant থেকেই প্রমাণ হয় যে vertex-গুলো level অনুযায়ী আসে; graph-এ BFS-এর একই প্রমাণ পর্ব ৫৯-এর §৮-এ।

নিচের ব্লক চারটি traversal একসঙ্গে চালায়, প্রতিটি vertex-এর ঠিকানা বানায়, আর ঠিকানা সাজিয়ে preorder-এর সঙ্গে মেলায়। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

from collections import deque
# (name, [children]) ; children are kept in order
T = ("সব", [("মুদি", [("চাল", []), ("ডাল", [])]),
            ("গ্যাজেট", [("ফোন", [("চার্জার", [])]), ("ল্যাপটপ", [])]),
            ("পোশাক", [])])
visits = 0
def pre(t):
    global visits; visits += 1
    return [t[0]] + [x for c in t[1] for x in pre(c)]
def post(t):
    return [x for c in t[1] for x in post(c)] + [t[0]]
def ino(t):                       # first subtree, root, then the rest
    if not t[1]:
        return [t[0]]
    return ino(t[1][0]) + [t[0]] + [x for c in t[1][1:] for x in ino(c)]
def level(t):
    q, out = deque([t]), []
    while q:
        u = q.popleft(); out.append(u[0]); q.extend(u[1])
    return out
def addresses(t, a=()):           # universal address: path of child numbers
    yield a, t[0]
    for i, c in enumerate(t[1], 1):
        yield from addresses(c, a + (i,))
P = pre(T)
print("preorder :", " ".join(P))
print("inorder  :", " ".join(ino(T)))
print("postorder:", " ".join(post(T)))
print("level    :", " ".join(level(T)))
A = list(addresses(T))
print("addresses:", ", ".join(".".join(map(str, a)) or "0" for a, _ in A))
lex = [name for a, name in sorted(A)]       # tuples compare lexicographically
print("preorder == lexicographic order of addresses:", lex == P)
print("nodes:", len(A), "| calls made by preorder:", visits)

preorder : সব মুদি চাল ডাল গ্যাজেট ফোন চার্জার ল্যাপটপ পোশাক
inorder  : চাল মুদি ডাল সব চার্জার ফোন গ্যাজেট ল্যাপটপ পোশাক
postorder: চাল ডাল মুদি চার্জার ফোন ল্যাপটপ গ্যাজেট পোশাক সব
level    : সব মুদি গ্যাজেট পোশাক চাল ডাল ফোন ল্যাপটপ চার্জার
addresses: 0, 1, 1.1, 1.2, 2, 2.1, 2.1.1, 2.2, 3
preorder == lexicographic order of addresses: True
nodes: 9 | calls made by preorder: 9

৩ · দুটি উপপাদ্য — ঠিকানার ক্রম আর Θ(n) সময়

প্রমাণ (গাছের vertex-সংখ্যা n-এর ওপর strong induction; ঠিকানাকে root থেকে মাপা পূর্ণসংখ্যার ক্রম ধরি, root-এর ঠিকানা খালি ক্রম):

1. ভিত্তি n = 1: একটিই vertex, দুই তালিকাই শুধু root. — base case
2. ধরুন n ≥ 2, root r, সন্তানদের subtree T₁, …, T_k, আর n-এর চেয়ে ছোট সব গাছে দাবি সত্য। T_i-এর প্রতিটি vertex-এর T-তে ঠিকানা হলো “i.” তারপর T_i-এর ভেতরে তার নিজের ঠিকানা। — সংজ্ঞা ১.২
3. Lexicographic order-এ খালি ক্রম সবার আগে, তাই r প্রথম। i < j হলে T_i-এর প্রতিটি ঠিকানা T_j-এর প্রতিটি ঠিকানার আগে, কারণ প্রথম স্থানেই i < j. — lexicographic-এর নিয়ম (খ)
4. একই T_i-এর দুটি ঠিকানার প্রথম অংশ i একই, তাই তুলনা বাকি অংশে, অর্থাৎ T_i-এর ভেতরের ঠিকানায়; হাইপোথিসিস অনুযায়ী সেই ক্রম preorder(T_i). — inductive hypothesis, |T_i| < n
5. তাই সাজানো তালিকা = r, preorder(T₁), …, preorder(T_k) = preorder(T). ∎ — সংজ্ঞা ২.১

এজন্যই বইয়ের সূচিপত্র (১, ১.১, ১.২, ২, …) আসলে অধ্যায়-গাছের preorder: অধ্যায়ের নাম আগে, তারপর তার উপ-অধ্যায়। একই কারণে কম্পিউটারের ফোল্ডার-তালিকা দেখানোর বহু টুল (যেমন সব ফাইলের পূর্ণ path সাজিয়ে দেখানো) প্রায় preorder দেয়।

1. একবার করে: n-এর ওপর strong induction. পাতার জন্য স্পষ্ট। n ≥ 2 হলে T₁, …, T_k-এর vertex-সেট পরস্পর আলাদা, আর root ছাড়া T-এর প্রতিটি vertex ঠিক একটি T_i-তে। হাইপোথিসিস অনুযায়ী প্রতিটি traversal(T_i) T_i-এর প্রত্যেককে একবার দেয়, আর root একবার যোগ হয়। — structural recursion-এর গঠন
2. ওপরের সীমা: vertex v-কে ঘিরে একটি ডাকে কাজ ≤ c · (1 + d(v)), যেখানে d(v) = v-এর সন্তান-সংখ্যা আর c একটি ধ্রুবক (নিজেকে লেখা, আর প্রতিটি সন্তানকে ডাকা ও ফল জোড়া)। — অনুমান
3. প্রতিটি অ-root vertex ঠিক একজনের সন্তান, তাই ∑_v d(v) = n − 1. মোট কাজ ≤ c · ∑(1 + d(v)) = c(2n − 1). — parent অনন্য
4. নিচের সীমা: তালিকায় nটি নাম লিখতেই অন্তত nটি ধাপ। মিলিয়ে সময় Θ(n). ∎

একটি সতর্কতা: ধাপ ২-এর অনুমান কোডের ওপর নির্ভর করে। §২-এর Python কোড তালিকা জোড়া দিতে নতুন list বানায়, যা গভীর গাছে বাড়তি খরচ আনতে পারে; বাস্তবের কোড একটি ফল-তালিকায় append করে বা generator দিয়ে Θ(n) রাখে। আরেকটি বাস্তব কথা: recursion-এর গভীরতা গাছের height-এর সমান, তাই খুব লম্বা “শিকলের মতো” গাছে recursion-এর সীমা ছাড়িয়ে যেতে পারে; তখন নিজের হাতে একটি stack রেখে একই traversal লেখা হয়। সেই কোড আর traversal-এর অনেক প্রয়োগ DSA কোর্সের পর্ব ২৬-এ।

প্রয়োগে কোন ক্রম কখন লাগে, তার একটি ছোট তালিকা:

• Preorder: মেনু বা ফোল্ডার-গাছ ইন্ডেন্ট করে ছাপা (আগে বিভাগের নাম, তারপর ভেতরের সব), গাছের কপি বানানো, গাছকে একটি লাইনে লিখে সংরক্ষণ।
• Postorder: প্রতিটি ফোল্ডারের মোট আকার হিসাব (আগে ভেতরের ফাইল-ফোল্ডার, তারপর নিজে), পুরো ফোল্ডার মুছে ফেলা (ভেতরের সব আগে মুছতে হয়), বিভাগ-গাছে মোট পণ্য গোনা, আর §৫-এর মতো expression-এর মান বের করা।
• Inorder: binary search tree-এ চাবিগুলো ছোট থেকে বড় ক্রমে দেয়; আর expression tree থেকে চেনা infix লেখা।
• Level order: root-এর সবচেয়ে কাছের vertex আগে খোঁজা, স্তর অনুযায়ী ছাপা, প্রতিটি level-এ কয়জন তা গোনা।

৪ · Expression tree — prefix, infix আর postfix

বাজারঘরের একটি অর্ডারে ৩ প্যাকেট চা (প্রতিটি 120 টাকা) আর ২ প্যাকেট বিস্কুট (প্রতিটি 45 টাকা), সঙ্গে 50 টাকার কুপন। মোট = 3 × 120 + 2 × 45 − 50. এই হিসাবের একটি গঠন আছে: আগে দুটি গুণ, তারপর যোগ, শেষে বিয়োগ। গঠনটি একটি গাছ।

এই গাছের তিনটি traversal তিনটি পরিচিত লেখার ধরন দেয়:

• Preorder → prefix বা Polish notation: − + × 3 120 × 2 45 50. Operator আগে, তারপর তার দুই operand.
• Postorder → postfix বা reverse Polish notation (RPN): 3 120 × 2 45 × + 50 −. দুই operand আগে, operator পরে।
• Inorder → infix: 3 × 120 + 2 × 45 − 50, আমাদের চেনা লেখা, তবে প্রয়োজনে বন্ধনীসহ।

নাম এসেছে পোল্যান্ডের যুক্তিবিদ Jan Łukasiewicz থেকে, যিনি ১৯২০-এর দশকে logic-এর সূত্র বন্ধনী ছাড়া লেখার জন্য prefix রূপ ব্যবহার করেন (ইতিহাস ভাবনার প্রশ্ন ১-এ)।

Infix-এ কেন বন্ধনী লাগে

8 − 3 − 2 লেখাটি দুটি আলাদা গাছ থেকে আসতে পারে: (8 − 3) − 2 = 3, অথবা 8 − (3 − 2) = 7. দুই গাছের বন্ধনী-ছাড়া inorder একই: 8, −, 3, −, 2. তাই inorder একা গাছ চেনায় না; infix-এ বন্ধনী, অথবা precedence (কোন operator আগে) আর associativity (সমান operator পরপর এলে কোনটি আগে) নিয়মের চুক্তি লাগে (§৬)। Prefix আর postfix-এ এই সমস্যা নেই: (8 − 3) − 2-এর postfix 8 3 − 2 −, আর 8 − (3 − 2)-এর 8 3 2 − −. এটি কাকতালীয় নয়।

1. (ক) Structural induction: পাতায় 1 = 0 + 1. (∘, E₁, E₂)-এ পাতা = (o₁ + 1) + (o₂ + 1) = (o₁ + o₂ + 1) + 1, আর operator o₁ + o₂ + 1. এটি পর্ব ১২-এর full binary tree-এর “পাতা = internal + 1”-এরই রূপ। — structural induction
2. (খ) ⇒ post(E) = post(E₁) post(E₂) ∘. হাইপোথিসিস অনুযায়ী post(E₁)-এর শুরু-অংশে ফারাক ≥ 1, আর পুরোটায় 1; তারপর post(E₂)-এর শুরু-অংশ যোগ হলে 1 + (≥ 1) ≥ 2; পুরো post(E₂) শেষে 1 + 1 = 2; শেষ ∘ যোগ করলে 2 − 1 = 1. — structural induction
3. (খ) ⇐ আর (গ) w-কে বাঁ থেকে পড়ে একটি stack-এ গাছ বানান: সংখ্যা হলে একক-পাতার গাছ push; operator হলে দুটি গাছ pop করে (প্রথমটি ডান, দ্বিতীয়টি বাঁ) নতুন গাছ push. Stack-এর আকার সবসময় ঠিক বর্তমান “ফারাক”, তাই শর্ত অনুযায়ী operator আসার আগে stack-এ অন্তত দুটি গাছ থাকে (operator যোগে ফারাক ≥ 1 থাকে মানে আগে ≥ 2 ছিল), আর শেষে ঠিক একটি গাছ। সেই গাছের postfix w (§৫-এর lemma-র মতো induction). — নির্মাণ
4. প্রতিটি ধাপ বাধ্যতামূলক: যেকোনো গাছ E-এর জন্য post(E) = w হলে এই প্রক্রিয়া ঠিক E-ই বানায়, কারণ প্রক্রিয়ায় কোনো বিকল্প নেই। তাই গাছ অনন্য। ∎ — নির্ধারিত (deterministic) প্রক্রিয়া

Prefix-এর জন্য একই কথা, শুধু ডান থেকে বাঁয়ে পড়ে। এই “একভাবেই পড়া যায়” ধারণা পর্ব ১২-এ logic-এর বন্ধনীসহ সূত্রের unique readability হিসেবে দেখেছেন; Łukasiewicz-এর লক্ষ্যই ছিল বন্ধনী বাদ দিয়েও তা রাখা।

৫ · Stack দিয়ে postfix-এর হিসাব আর তার প্রমাণ

Postfix-এর সবচেয়ে বড় সুবিধা: হিসাব করতে বন্ধনী বা precedence জানতে হয় না, একবার বাঁ থেকে ডানে পড়লেই চলে। দরকার শুধু একটি stack, যেখানে শেষে রাখা জিনিস আগে বের হয়, যেমন বিয়েবাড়িতে থালার স্তূপ। নিয়ম:

• টোকেন সংখ্যা হলে stack-এ push.
• টোকেন operator ∘ হলে প্রথমে b = pop, তারপর a = pop, আর a ∘ b push. খেয়াল করুন, যেটি প্রথমে বের হয় সেটি ডান operand.
• শেষে stack-এ ঠিক একটি সংখ্যা থাকে: সেটিই মান।

1321203×425456×7+8509−

কেন এই সরল নিয়ম সবসময় ঠিক মান দেয়? চাবি হলো একটু শক্তিশালী একটি দাবি প্রমাণ করা, যাতে stack-এ আগে থেকে কিছু থাকলেও কথা খাটে। “শক্ত দাবি প্রমাণ সহজ” কৌশলটি পর্ব ১২-এ structural induction-এর সঙ্গে দেখেছেন।

প্রমাণ (E-এর ওপর structural induction):

1. Basis: E একটি সংখ্যা x. post(E) = x, একটি push; ফল S · [x] = S · [val(E)]. — নিয়ম ১
2. Recursive step: E = (∘, E₁, E₂), তাই post(E) = post(E₁), post(E₂), ∘. হাইপোথিসিস E₁ আর E₂-এর জন্য যেকোনো শুরুর stack-এ খাটে। — সংজ্ঞা ২.১
3. S থেকে post(E₁) চালালে stack S · [v₁], যেখানে v₁ = val(E₁), আর S অক্ষত। — হাইপোথিসিস, শুরু S
4. এবার S · [v₁] থেকে post(E₂) চালালে S · [v₁, v₂], আর S · [v₁] অক্ষত। — হাইপোথিসিস, শুরু S · [v₁]
5. শেষ টোকেন ∘: প্রথম pop v₂ = b, দ্বিতীয় pop v₁ = a, push a ∘ b = v₁ ∘ v₂ = val(E). Stack S · [val(E)], আর S-এর কিছুই pop হয়নি। ∎ — নিয়ম ২, val-এর সংজ্ঞা

খালি S নিলে অনুসিদ্ধান্ত: post(E) চালালে শেষে stack-এ শুধু val(E). ধাপ ৪-এ হাইপোথিসিসটি খালি stack নয়, S · [v₁] দিয়ে শুরু হয়েছে; তাই শুধু “খালি stack থেকে শুরু” দাবি নিয়ে induction করলে প্রমাণ আটকে যায়। ধাপ ৫ দেখায় pop-এর ক্রম কেন গুরুত্বপূর্ণ: + আর ×-এ ক্রম উল্টালেও ফল একই (commutative), কিন্তু − আর ÷-এ নয়।

Prefix-এর হিসাবেও একই stack: টোকেন ডান থেকে বাঁয়ে পড়ুন, আর operator এলে এবার প্রথম pop-ই বাঁ operand. বিকল্পভাবে prefix সরাসরি recursion দিয়ে পড়া যায়: প্রথম টোকেন operator হলে বাকি থেকে একটি পুরো expression পড়ুন (বাঁ), তারপর আরেকটি (ডান)। নিচের ব্লক এলোমেলো expression tree বানিয়ে তিনটি পদ্ধতি মেলায়: postfix-stack, prefix-stack, আর বন্ধনীসহ infix লিখে Python-এর নিজের eval. সংখ্যাগুলো Fraction (ভগ্নাংশ), তাই ভাগে দশমিকের ভুল নেই। eval এখানে নিরাপদ, কারণ string-টি আমাদের কোডই বানায়, আর তাতে শুধু অঙ্ক, চার operator আর বন্ধনী থাকে।

import random; from fractions import Fraction as F
OPS = {"+": lambda a, b: a + b, "-": lambda a, b: a - b,
       "*": lambda a, b: a * b, "/": lambda a, b: a / b}
def rand_tree(depth):                  # leaf = int, node = (op, left, right)
    if depth == 0 or random.random() < 0.3:
        return random.randint(1, 9)
    return (random.choice("+-*/"), rand_tree(depth - 1), rand_tree(depth - 1))
def prefix(t):  return [t] if isinstance(t, int) else [t[0]] + prefix(t[1]) + prefix(t[2])
def postfix(t): return [t] if isinstance(t, int) else postfix(t[1]) + postfix(t[2]) + [t[0]]
def infix(t):                          # fully parenthesised, ready for eval
    return f"F({t})" if isinstance(t, int) else f"({infix(t[1])} {t[0]} {infix(t[2])})"
def eval_postfix(tokens):              # left to right, one stack
    st = []
    for x in tokens:
        if x in OPS:
            b = st.pop(); a = st.pop()  # right operand comes off first
            st.append(OPS[x](a, b))
        else:
            st.append(F(x))
    assert len(st) == 1
    return st[0]
def eval_prefix(tokens):               # same idea, read right to left
    st = []
    for x in reversed(tokens):
        st.append(OPS[x](st.pop(), st.pop()) if x in OPS else F(x))
    return st[0]
t = ("-", ("+", ("*", 3, 120), ("*", 2, 45)), 50)
print(*prefix(t), "|", *postfix(t), "|", eval_postfix(postfix(t)))
random.seed(66); ok = skipped = 0
for _ in range(2000):
    t = rand_tree(4)
    try: truth = eval(infix(t), {"F": F})
    except ZeroDivisionError: skipped += 1; continue
    assert eval_postfix(postfix(t)) == truth == eval_prefix(prefix(t)); ok += 1
print(ok, "random trees: postfix stack = prefix stack = eval;", skipped, "had division by 0")

- + * 3 120 * 2 45 50 | 3 120 * 2 45 * + 50 - | 400
1971 random trees: postfix stack = prefix stack = eval; 29 had division by 0

৬ · Infix থেকে postfix — precedence, associativity আর shunting-yard

মানুষ infix লেখে, কিন্তু যন্ত্রের জন্য postfix বা গাছ সুবিধাজনক। তাই প্রতিটি calculator আর compiler-কে infix থেকে গাছ বা postfix বানাতে হয়। এর জন্য দুটি চুক্তি লাগে:

• Precedence: × আর ÷ “বেশি শক্ত করে বাঁধে”, + আর −-এর চেয়ে। তাই 3 + 4 × 5 মানে 3 + (4 × 5) = 23.
• Associativity: একই precedence-এর operator পরপর এলে কোনটি আগে। +, −, ×, ÷ left-associative: 8 − 3 − 2 = (8 − 3) − 2 = 3. Python-এর ঘাত ** right-associative: 2 ** 3 ** 2 = 2 ** (3 ** 2) = 512, 64 নয়।

Edsger Dijkstra-র shunting-yard পদ্ধতি (১৯৬০-এর দশকের শুরুতে বর্ণিত বলে উল্লেখ করা হয়; নামটি রেলের শান্টিং ইয়ার্ড থেকে, যেখানে বগি পাশের লাইনে সরিয়ে রেখে পরে ক্রম বদলে জোড়া হয়) একটি operator-stack রাখে। টোকেন বাঁ থেকে পড়া হয়:

1. সংখ্যা সরাসরি output-এ যায়।
2. Operator ∘ এলে, যতক্ষণ stack-এর ওপরে এমন operator আছে যা ∘-এর চেয়ে বেশি precedence-এর, অথবা সমান precedence-এর আর ∘ left-associative, ততক্ষণ সেটি pop করে output-এ যোগ করুন; তারপর ∘ push.
3. “(” push হয়; “)” এলে “(” না পাওয়া পর্যন্ত সব pop করে output-এ, তারপর “(” ফেলে দিন।
4. শেষে stack-এ যা থাকে, ওপর থেকে একে একে output-এ।

নিয়ম ২-এর মর্ম: stack-এর ওপরের operator যদি নতুনটির চেয়ে আগে হিসাব হওয়ার কথা, তবে তার দুই operand ইতিমধ্যে output-এ আছে, তাই এখনই তাকে বের করে দেওয়া নিরাপদ। 8 − 3 − 2-এ দ্বিতীয় − আসার সময় প্রথম −-কে বের করে দেয় (সমান precedence, left-associative), ফলে 8 3 − 2 −. Right-associative **-এর জন্য “সমান হলে বের করো” অংশটি বাদ যায়, তাই 2 3 2 ** **. Unary minus (একটি operand-এর বিয়োগ চিহ্ন) আলাদা টোকেন হিসেবে সামলাতে হয়; Python-এ -2 ** 2 = −4, কারণ ** unary minus-এর চেয়ে শক্ত করে বাঁধে। পূর্ণ কোড, বন্ধনী মেলানো আর ভুল ইনপুট সামলানো DSA কোর্সের পর্ব ১৩-এ।

কাজের বেলায় compiler infix থেকে সরাসরি গাছ বানায়, যার নাম abstract syntax tree (AST): বন্ধনী আর ফাঁকা জায়গার মতো “লেখার খুঁটিনাটি” বাদ দিয়ে শুধু গঠন। Python নিজেই আপনার কোড প্রথমে AST-তে রূপান্তর করে, তারপর bytecode বানায় (Python প্রোগ্রামিং কোর্সের পর্ব ০৫)। আর Python-এর ast module সেই গাছ আমাদের হাতে দেয়। তাই একটি সুন্দর যাচাই সম্ভব: আমাদের shunting-yard-এর output আর Python-এর নিজের AST-এর postorder কি এক?

import ast, random
PREC = {"+": 1, "-": 1, "*": 2, "/": 2}          # all left-associative
def shunting_yard(text):
    out, ops = [], []
    for tk in text.replace("(", " ( ").replace(")", " ) ").split():
        if tk.isdigit(): out.append(tk)
        elif tk == "(": ops.append(tk)
        elif tk == ")":
            while ops[-1] != "(": out.append(ops.pop())
            ops.pop()                             # throw away "("
        else:                                     # pop while top binds as tight
            while ops and ops[-1] != "(" and PREC[ops[-1]] >= PREC[tk]:
                out.append(ops.pop())
            ops.append(tk)
    return out + ops[::-1]
SYM = {ast.Add: "+", ast.Sub: "-", ast.Mult: "*", ast.Div: "/"}
def ast_postfix(n):                               # postorder walk of Python's AST
    if isinstance(n, ast.Constant): return [str(n.value)]
    return ast_postfix(n.left) + ast_postfix(n.right) + [SYM[type(n.op)]]
def rand_infix(d):                 # minimal brackets: (text, precedence)
    if d == 0 or random.random() < 0.3: return str(random.randint(1, 9)), 3
    op = random.choice("+-*/"); (a, pa), (b, pb) = rand_infix(d - 1), rand_infix(d - 1)
    if pa < PREC[op]: a = f"({a})"
    if pb <= PREC[op]: b = f"({b})"               # right side: equal needs ()
    return f"{a} {op} {b}", PREC[op]
s = "3 * 120 + 2 * 45 - 50"
print(" ".join(shunting_yard(s)))
print("8 - 3 - 2 ->", " ".join(shunting_yard("8 - 3 - 2")), "=", eval("8 - 3 - 2"))
random.seed(13); same = 0
for _ in range(1000):
    text, _ = rand_infix(4)
    tree = ast.parse(text, mode="eval").body
    assert shunting_yard(text) == ast_postfix(tree); same += 1
print(same, "random infix strings: shunting-yard == postorder of Python's AST")
print("example:", text, "->", " ".join(shunting_yard(text)))

3 120 * 2 45 * + 50 -
8 - 3 - 2 -> 8 3 - 2 - = 3
1000 random infix strings: shunting-yard == postorder of Python's AST
example: 1 * (6 - (7 - 4) - 8) -> 1 6 7 4 - - 8 - *

৭ · Traversal থেকে গাছ ফেরত — কখন অনন্য, কখন নয়

বাজারঘরের সার্ভার ডেলিভারি-জোনের একটি binary tree শুধু দুটি তালিকা হিসেবে সংরক্ষণ করে। প্রশ্ন: কোন দুটি তালিকা রাখলে গাছটি নিশ্চিতভাবে ফিরে পাওয়া যায়? এই অংশে binary tree-র প্রতিটি vertex-এর লেবেল আলাদা ধরে নিচ্ছি; একই লেবেল একাধিকবার থাকলে কোনো জোড়াই যথেষ্ট নয় (যেমন সব লেবেল A হলে তিনটি তালিকাই শুধু A, A, A).

প্রমাণ (vertex-সংখ্যা n-এর ওপর strong induction):

1. ভিত্তি n = 0: দুটিই খালি গাছ। — base case
2. n ≥ 1: preorder-এর প্রথম লেবেল r দুই গাছেরই root. — preorder-এ root আগে
3. লেবেলগুলো আলাদা, তাই inorder-এ r ঠিক এক জায়গায়, ধরুন অবস্থান k + 1-এ। Inorder = (বাঁ subtree-র inorder), r, (ডান subtree-র inorder), তাই দুই গাছেই বাঁ subtree-তে ঠিক kটি vertex, আর সেগুলো inorder-এর প্রথম k লেবেল। — inorder-এর সংজ্ঞা
4. Preorder = r, (বাঁ-র preorder), (ডান-র preorder), আর বাঁ-র preorder-এ kটি লেবেল; তাই দুই গাছেরই বাঁ subtree-র preorder হলো preorder-এর ২য় থেকে (k + 1)-তম লেবেল, ডান subtree-র বাকিগুলো। — দৈর্ঘ্য মেলানো
5. দুই গাছের বাঁ subtree-র preorder আর inorder একই, আকার k < n; হাইপোথিসিস অনুযায়ী বাঁ subtree দুটি একই। ডান subtree-র জন্যও একই কথা। Root, বাঁ আর ডান এক বলে গাছ দুটি এক। ∎ — inductive hypothesis

প্রমাণটি নিজেই একটি algorithm: preorder-এর প্রথমটি root, inorder-এ তাকে খুঁজে বাঁ-ডান ভাগ, তারপর দুই ভাগে একই কাজ। নিচের stepper ৯ vertex-এর একটি গাছ ফেরত আনে।

1পুরো গাছ: root A2A-এর বাঁ: root B3B-এর ডান: root E4A-এর ডান: root C5C-এর ডান: root F6যাচাই: postorder

Preorder + postorder কেন যথেষ্ট নয়

সবচেয়ে ছোট পাল্টা-উদাহরণ দুটি vertex-এর: root A আর একটি সন্তান B. B বাঁ সন্তান হোক বা ডান, দুই গাছেই preorder A B আর postorder B A. Preorder আর postorder দুটোই root-কে এক প্রান্তে রাখে, তাই কোনটি বাঁ আর কোনটি ডান, তা ভাগ করার মতো কোনো “মাঝের চিহ্ন” পাওয়া যায় না; একমাত্র সন্তানের দিক হারিয়ে যায়। প্রতিটি “একমাত্র-সন্তান” vertex এই দ্বিধা একবার করে আনে। Brute force-এ (n ≤ 7 পর্যন্ত সব গাছ) দেখা যায়, একই preorder আর postorder-ওয়ালা গাছ ঠিক 2^sটি, যেখানে s = একমাত্র-সন্তানওয়ালা vertex-এর সংখ্যা।

উল্টো দিকে, full binary tree-এ (প্রতিটি internal vertex-এর ঠিক দুটি সন্তান) preorder আর postorder যথেষ্ট। প্রমাণের ধারণা: preorder-এর দ্বিতীয় লেবেল x হলো বাঁ সন্তান (n ≥ 3 হলে বাঁ সন্তান থাকতেই হয়)। Postorder-এ বাঁ subtree আগে আসে আর x তার শেষ লেবেল, তাই postorder-এ x-এর অবস্থান বাঁ subtree-র আকার বলে দেয়; বাকিটা উপপাদ্য ৭.১-এর মতো induction.

একটি traversal মেলে কয়টি গাছে

Preorder 1, 2, …, n দেওয়া থাকলে কয়টি binary tree এর সঙ্গে মেলে? প্রতিটি আকার (shape) নিন, আর vertex-গুলোকে preorder-এ 1, 2, …, n নাম দিন; তাতে প্রতিটি আকার থেকে ঠিক একটি গাছ পাওয়া যায়, আর আলাদা আকার আলাদা গাছ দেয়। তাই সংখ্যাটি n vertex-এর binary tree-র আকারের সংখ্যা, অর্থাৎ Catalan সংখ্যা C_n = C(2n, n)/(n + 1): 1, 2, 5, 14, 42, 132, … (গণনার প্রমাণ পর্ব ৩৭-এ)। এটি একটি bijection যুক্তি। Inorder দিলেও একই সংখ্যা। কিন্তু preorder আর inorder দুটি দিলে উপপাদ্য ৭.১ অনুযায়ী বড়জোর একটি।

import random
from collections import Counter
# binary tree: None or (label, left, right); labels are distinct
def pre(t):  return [] if t is None else [t[0]] + pre(t[1]) + pre(t[2])
def ino(t):  return [] if t is None else ino(t[1]) + [t[0]] + ino(t[2])
def post(t): return [] if t is None else post(t[1]) + post(t[2]) + [t[0]]
def rebuild(p, i):                       # preorder + inorder -> tree
    if not p: return None
    k = i.index(p[0])                    # root splits the inorder list
    return (p[0], rebuild(p[1:k + 1], i[:k]), rebuild(p[k + 1:], i[k + 1:]))
def shapes(n):                           # every binary tree shape with n nodes
    if n == 0: return [None]
    return [(None, l, r) for k in range(n)
            for l in shapes(k) for r in shapes(n - 1 - k)]
def label_preorder(s, it):               # name the nodes 1, 2, ... in preorder
    if s is None: return None
    v = next(it)
    return (v, label_preorder(s[1], it), label_preorder(s[2], it))
t9 = rebuild(list("ABDEGCFHI"), list("DBGEACHFI"))
print("postorder:", "".join(post(t9)))
random.seed(7); ok = 0
for n in range(1, 8):
    for s in shapes(n):
        labels = random.sample(range(100), n)
        t = label_preorder(s, iter(labels))
        assert rebuild(pre(t), ino(t)) == t; ok += 1
print(ok, "trees (all shapes, n <= 7): rebuilt exactly from preorder + inorder")
for n in range(1, 7):
    trees = [label_preorder(s, iter(range(1, n + 1))) for s in shapes(n)]
    pp = Counter((tuple(pre(t)), tuple(post(t))) for t in trees)
    print(f"n={n}: {len(trees)} trees share preorder 1..{n};",
          f"(pre, post) pairs {len(pp)}, worst pair fits {max(pp.values())} trees")

postorder: DGEBHIFCA
625 trees (all shapes, n <= 7): rebuilt exactly from preorder + inorder
n=1: 1 trees share preorder 1..1; (pre, post) pairs 1, worst pair fits 1 trees
n=2: 2 trees share preorder 1..2; (pre, post) pairs 1, worst pair fits 2 trees
n=3: 5 trees share preorder 1..3; (pre, post) pairs 2, worst pair fits 4 trees
n=4: 14 trees share preorder 1..4; (pre, post) pairs 4, worst pair fits 8 trees
n=5: 42 trees share preorder 1..5; (pre, post) pairs 9, worst pair fits 16 trees
n=6: 132 trees share preorder 1..6; (pre, post) pairs 21, worst pair fits 32 trees

৮ · পরীক্ষার অঙ্ক আর একটি ভুল প্রমাণ

অঙ্ক ১: Infix থেকে prefix আর postfix

(7 − 2) × (4 + 6) ÷ 5-এর expression tree আঁকুন (×, ÷ left-associative), আর prefix, postfix ও মান লিখুন।

1. × আর ÷ সমান precedence, বাঁ থেকে: ((7 − 2) × (4 + 6)) ÷ 5. Root ÷, বাঁ subtree × (যার বাঁয়ে 7 − 2, ডানে 4 + 6), ডান subtree পাতা 5.
2. Prefix (preorder): ÷ × − 7 2 + 4 6 5.
3. Postfix (postorder): 7 2 − 4 6 + × 5 ÷.
4. মান: 5 × 10 ÷ 5 = 10 (scratch-এ Python-এর AST দিয়ে prefix, postfix আর মান মেলানো)।

অঙ্ক ২: Postfix আর prefix-এর মান

(ক) 6 2 3 + − 3 8 2 ÷ + × আর (খ) − × 2 + 3 5 ÷ 12 4-এর মান কত?

1. (ক) Stack: [6, 2, 3] → + → [6, 5] → − → [1] → [1, 3, 8, 2] → ÷ → [1, 3, 4] → + → [1, 7] → × → [7]. মান 7.
2. (খ) ডান থেকে পড়ে: [4, 12] → ÷ দেয় 12 ÷ 4 = 3 → [3, 5, 3] → + দেয় 3 + 5 = 8 → [3, 8, 2] → × দেয় 2 × 8 = 16 → [3, 16] → − দেয় 16 − 3 = 13. Infix-এ 2 × (3 + 5) − 12 ÷ 4 (দুটিই scratch-এ মেলানো)।

অঙ্ক ৩: দুই traversal থেকে তৃতীয়টি

একটি binary tree-র preorder P Q S T R U আর inorder S Q T P U R. Postorder কী?

1. Root P; inorder-এ বাঁয়ে S Q T, ডানে U R. বাঁ অংশের preorder Q S T, ডান অংশের R U.
2. বাঁ: root Q, বাঁয়ে S, ডানে T. ডান: root R, inorder U R, তাই U হলো R-এর বাঁ সন্তান।
3. Postorder: S T Q, তারপর U R, শেষে P: S T Q U R P (scratch-এ rebuild দিয়ে মেলানো)।

অঙ্ক ৪: গোনা

(ক) ৫ vertex-এর কয়টি binary tree-র preorder 1 2 3 4 5? (খ) কয়টি binary tree-র preorder A B C আর postorder C B A? উত্তর: (ক) C₅ = C(10, 5)/6 = 42. (খ) গাছ দুটির preorder আর postorder মিলাতে হলে A-এর একমাত্র সন্তান B, আর B-এর একমাত্র সন্তান C; প্রতিটি বাঁ বা ডান, তাই 2 × 2 = 4 (দুটিই scratch-এ সব গাছ গুনে মেলানো)।

প্রমাণের ভুল ধরুন: “preorder আর postorder গাছ চেনায়”

একজন লিখলেন: “n-এর ওপর induction. Preorder-এর প্রথম লেবেল root r, postorder-এর শেষ লেবেলও r. Preorder-এর দ্বিতীয় লেবেল x হলো বাঁ সন্তান। Postorder-এ x-এর আগে পর্যন্ত (x সহ) যা আছে তা বাঁ subtree, বাকিটা ডান subtree. দুই অংশেই হাইপোথিসিস খাটে, তাই গাছ অনন্য। ∎”

ভুল কোথায়: “preorder-এর দ্বিতীয় লেবেল বাঁ সন্তান” দাবিটি শুধু তখন সত্য, যখন root-এর বাঁ সন্তান আছে। Root-এর শুধু ডান সন্তান থাকলে দ্বিতীয় লেবেল ডান সন্তান, আর প্রমাণ ভুল করে তাকে বাঁ ধরে। পাল্টা-উদাহরণ: A-এর একমাত্র সন্তান B, বাঁয়ে বা ডানে; দুই গাছেই preorder A B, postorder B A. প্রমাণটি একটি গোপন ধারণার ওপর দাঁড়িয়ে: “প্রতিটি internal vertex-এর দুটি সন্তান”। ঠিক সেই শর্ত যোগ করলে (full binary tree) যুক্তিটি সঠিক হয়, §৭-এর মতো।

৯ · AI-এর যুগে — traversal আর notation-এর উত্তর যাচাই

Traversal-এর প্রশ্নে AI সহকারী সংজ্ঞা সাধারণত ঠিক বলে, কিন্তু হাতে-কলমে ক্রম লিখতে গিয়ে একটি subtree বাদ দেয়, operand-এর ক্রম উল্টায়, আর “অনন্য” দাবিতে শর্ত ভুলে যায়। কয়েকটি নিয়মিত ভুল আর ধরার উপায়:

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

• গাছটি নিজে এঁকেছি, আর প্রতিটি vertex তালিকায় ঠিক একবার এসেছে
• Postfix হিসাব নিজের stack কোডে চালিয়ে মান মিলিয়েছি, বিশেষত − আর ÷
• Infix-এর মান Python-এর eval বা ast দিয়ে মিলিয়েছি
• “অনন্য” দাবির শর্ত (আলাদা লেবেল, কোন দুই traversal) পরীক্ষা করেছি
• Induction প্রমাণে হাইপোথিসিস যথেষ্ট শক্ত (যেমন যেকোনো শুরুর stack) কি না দেখেছি
• উদ্ধৃত নাম, সাল আর উৎস বিশ্বস্ত textbook-এ মিলিয়েছি

সবচেয়ে কাজের অভ্যাস: AI যে ক্রম বা মান দিক, সেটি ১০ লাইনের একটি traversal বা stack কোডে চালিয়ে মেলান। ছোট গাছে সব আকার brute force করেও দাবি পরীক্ষা করা যায়, যেমন §৭-এর ব্লকে।