Parse Tree

အခု Tree ကို အသံုးျပဳျပီးေတာ့ parse tree တစ္ခု ကို ဖန္တီးရေအာင္။ နားလည္ ေအာင္ သေဘာေျပာရရင္ေတာ့ ((9 + 4) * (6 − 2)) ကို parse tree ထုတ္လိုက္ရင္ ေအာက္ပါ ပံုအတိုင္း ထြက္လာပါလိမ့္မယ္။

အထက္ပါ diagram ကို ၾကည့္လိုက္ရင္ ရိုးရွင္းပါတယ္။ ၉ ႏွင့္ ၄ ကို အရင္ ေပါင္းမယ္။ ျပီးရင္ ၆ ထဲ က ၂ ကို ႏႈတ္မယ္။ ျပီးရင္ ျပန္ေျမွာက္မယ္။

အခု ကၽြန္ေတာ္တုိ့ေတြအေနနဲ႕ User က ေပးလိုက္သည့္ parser ေပၚမွာ မူတည္ျပီးေတာ့ parse tree တစ္ခု တည္ေဆာက္ပါမယ္။

ဦးစြာ ကၽြန္ေတာ္တုိ့ေတြ တည္ေဆာက္ဖို့အတြက္ rule ေလးေတြ ၾကည့္ပါမယ္။

၁။ ( ပါ လာခဲ့ရင္ node အသစ္တစ္ခုကို လက္ရိွ node ရဲ႕ ဘယ္ဘက္ child မွာ တည္ေဆာက္ဖို့ လိုပါတယ္။

၂။ + , - , * , / တစ္ခု ျဖစ္ရင္ေတာ့ လက္ရိွ node ရဲ႕ value ကို ရလာသည့္ သေကၤတ ကို ထည့္ပါမယ္။ ညာဘက္မွာ node အသစ္တစ္ခု တည္ေဆာက္ပါမယ္။

၃။ value ကေတာ့ နံပတ္ ျဖစ္ေနရင္ လက္ရိွ node ရဲ႕ value ကို အဲဒီ နံပတ္ ထည့္မယ္ ျပီးရင္ သူ႕ရဲ႕ parent node ကို ျပန္သြားပါမယ္။ ဒါေၾကာင့္ current node က သူ႕ရဲ႕ parent node ျဖစ္သြားပါလိမ့္မယ္။

၄။ ) ေတြ႕ခဲ့ရင္လည္း parent node ဆီ ျပန္သြားဖို့ပါပဲ။

အခု ကၽြန္ေတာ္တုိ႕ေတြ ((9 + 4) * (6 − 2)) ကို စမ္းၾကည့္ရေအာင္။

( ေတြ႕သည့္ အတြက္ left child တစ္ခု တည္ေဆာက္ပါမယ္။

( ထပ္ေတြ႕သည့္ အတြက္ ထပ္ျပီးေတာ့ left child တစ္ခု ထပ္ေဆာက္ပါမယ္။

9 ကို ေတြ႕သည့္အတြက္ value ကို ထည့္ျပီးေတာ့ parent node ကို ျပန္သြားပါမယ္။

+ ကို ေတြ႕သည့္ အတြက္ေၾကာင့္ value ထည့္ျပီးေတာ့ right child တစ္ခု ေဆာက္ပါမယ္။

4 ကို ေတြ႕သည့္ အတြက္ေၾကာင့္ value ထည့္ျပီးေတာ့ parent ကို ျပန္သြားပါမယ္။

) ကို ေတြ႕သည့္ အတြက္ေၾကာင့္ parent node ကို ျပန္သြားပါမယ္။

* ကို ေတြ႕သည့္ အတြက္ေၾကာင့္ value ထည့္ျပီးေတာ့ right child ကို ေဆာက္ပါမယ္။

( ကို ေတြ႕သည့္ အတြက္ ေၾကာင့္ left child ေဆာက္ပါမယ္။

6 ကို ေတြ႕သည့္ အတြက္ေၾကာင့္ value ထည့္မယ္။ parent ကို ျပန္သြားပါမယ္။

- ကို ေတြ႕သည့္ အတြက္ေၾကာင့္ value ထည့္မယ္။ right child ကို ေဆာက္ပါမယ္။

2 ကို ေတြ႕သည့္ အတြက္ေၾကာင့္ value ထည့္မယ္။ parent node ကို ျပန္သြားမယ္။

) ကို ေတြ႕သည့္ အတြက္ေၾကာင့္ parent node ကို ထပ္သြားပါမယ္။

) ကို ေတြ႕တယ္။ parent ကို ထပ္သြားတယ္။ ဒါေပမယ့္ parent မရိွေတာ့သည့္ အတြက္ current node မွာ ဘာမွ မရိွေတာ့ပါဘူး။ ကၽြန္ေတာ္တုိ့လည္း parse tree ဆြဲလို႕ျပီးပါျပီ။

အခု ကၽြန္ေတာ္တို႕ parse tree ကုိ code အေနနဲ႕ ေရးၾကည့္ရေအာင္။

from binarytree import BinaryTree from stack import Stack def build_parse_tree(fp_exp): fp_list = fp_exp.split() p_stack = Stack() e_tree = BinaryTree('') p_stack.push(e_tree) current_tree = e_tree for i in fp_list: if i == '(': current_tree.insert_left('') p_stack.push(current_tree) current_tree = current_tree.get_left_child() elif i not in ['+', '-', '*', '/', ')']: current_tree.set_root_val(int(i)) parent = p_stack.pop() current_tree = parent elif i in ['+', '-', '*', '/']: current_tree.set_root_val(i) current_tree.insert_right('') p_stack.push(current_tree) current_tree = current_tree.get_right_child() elif i == ')': current_tree = p_stack.pop() else: raise ValueError return e_tree pt = build_parse_tree("( ( 9 + 4 ) * ( 6 - 2 ) )") pt.postorder()

အခု code မွာ ကၽြန္ေတာ္တုိ့ေတြ binary tree နဲ႕ stack ကို သံုးထားတာကို ေတြ႕ႏိုင္ပါတယ္။ အဲဒီမွာ ထူးထူးျခားျခား postorder ဆိုတာ ပါလာပါတယ္။ ဒီအေၾကာင္းကို ေနာက္ အခန္းမွာ ဆက္ရွင္းျပပါမယ္။

results matching ""

    No results matching ""