ساختن یک درخت عبارت چگونه است ؟
ساختن یک درخت عبارت چگونه است ؟
در این بخش، عبارات infix را تجزیـه مـیکنـیم و درخـت عبـارت متنـاظر بـا آن را ایجـاد میکنیم. براي مثال، عبارت 9)*7+3 (درخت زیر را نتیجه میدهد: توجه کنید که ما با حذف اسامی مشخصهها نمودار را سادهتر کردیم. تجزیهگري که خواهیم نوشت، بر روي عباراتی شامل اعـداد، پرانتزهـا و عملگرهـاي + و * کـار میکند. ما فرض میکنیم رشتۀ ورودي قبلاً درون یک لیست پایتون بـه تعـدادي تـوکن تقسـیم شـده است. لیست توکن براي عبارت 9*7+3 به این صورت است:
[‘(‘, 3, ‘+’, 7, ‘)’, ‘*’, 9, ‘end’]
توکن end مشخص میکند که لیست پایان یافته و تجزیهگر را از ادامۀ کار باز میدارد. اولین تابعی که مینویسیم getToken است که لیستی از توکنها و یـک تـوکن خـاص را بـه عنوان پارامتر میگیرد. این تابع توکن مورد نظر را با اولین توکن در لیست مقایسه میکند، اگـر بـا هـم برابـر بودنـد آن را حـذف مـیکنـد و مقـدار true را برمـیگردانـد؛ در غیـر ایـنصـورت false را برمیگرداند:
def getToken(tokenList, expected):
if tokenList[0] == expected:
del tokenList[0]
return 1
else:
return 0
از آنجا که tokenList به یک شیء تغییرپذیر اشاره میکند، تغییراتی که در اینجا بـهوجـود میآید از هر متغیر دیگري که به همین شیء اشاره کند، قابل رؤیتند. تابع بعدي، getNumber ،عملوندها را اداره میکند. اگر توکن بعـدي در tokenList یـک عدد باشد، getNumber آن را حذف میکند و یک گره برگ شامل آن عدد را برمـیگردانـد، در غیـر اینصورت None را برمیگرداند:
def getNumber(tokenList):
x = tokenList[0]
if type(x) != type(0): return None
del tokenList[0]
return Tree (x, None, None)
قبـل از ادامـه، بایـد getNumber را بـه تنهـایی آزمـایش کنـیم. مـا لیسـتی از اعـداد را بـه tokenList نسبت میدهیم. عضو اول را در میآوریم، نتیجه را چاپ میکنیم و سپس هر چه که از لیست توکنها باقی مانده بود را چاپ مینماییم:
>> tokenList = [9, 11, ‘end’]
>>> x = getNumber(tokenList)
>>> printTreePostorder(x)
9
>>> print tokenList
[11, ‘end’]
متد دیگري که نیاز داریم، getProduct است که یک درخت عبارت براي حاصـلضـربهـا میسازد. یک حاصلضرب ساده دو عدد بهعنوان عملوند دارد، مثل 7*3
دراینجا نسخهاي از getProduct آمده است که بر روي حاصلضربهاي ساده کار میکند.
def getProduct(tokenList):
a = getNumber(tokenList)
if getToken(tokenList, ‘*’):
b = getNumber(tokenList)
return Tree (‘*’, a, b)
else:
return a
با فرض بر اینکه getNumber درست کار میکند و یک درخت منحصر بهفـرد برمـیگردانـد، عملوند اول را به a نسبت میدهیم. اگر کاراکتر بعدي * باشد، عدد دوم را میگیریم و با a ،b و عملگـر یک درخت عبارت تولید میکنیم. اگر کاراکتر بعدي چیز دیگري باشد، آنگاه تنها گره برگ با a را برمیگردانیم. در اینجا دو مثـال اورده شده است:
>> tokenList = [9, ‘*’, 11, ‘end’]
>>> tree = getProduct(tokenList)
>>> printTreePostorder(tree)
9 11 *
>>> tokenList = [9, ‘+’, 11, ‘end’]
>>> tree = getProduct(tokenList)
>>> printTreePostorder(tree)
9
مثال دوم به این نکته اشاره دارد که ما یک عملوند واحد را بهعنوان نـوعی حاصـلضـرب تلقـی کردهایم. این نوع تعریف از ”حاصلضرب“، غیر شهودي است، اما مفید بهنظر میرسد. با یک تغییر کوچک در getProduct ،میتوانیم بر روي یک ضرب طولانی دلخواه کار کنیم:
def getProduct(tokenList):
a = getNumber(tokenList)
if getToken(tokenList, ‘*’):
b = getProduct(tokenList) # this line changed
return Tree (‘*’, a, b)
else:
return a
به بیان دیگر، یک ضرب میتواند یک ضرب یگانه باشد و یا یک درخت با * در ریشه، یک عـدد در سمت چپ و یک ضرب در سمت راست. این نوع از تعریف بازگشـتی بایـد تمـرین شـود تـا مـأنوس بهنظر برسد. اجازه دهید نسخۀ جدید را با یک ضرب پیچیده آزمایش کنیم:
>>> tokenList = [2, ‘*’, 3, ‘*’, 5 , ‘*’, 7, ‘end’]
>>> tree = getProduct(tokenList)
>>> printTreePostorder(tree)
2 3 5 7 * * *
در ادامه توانایی تجزیۀ اعمال جمع را اضافه میکنیم. باز هم از یک تعریف غیرشهودي ”جمـع“ استفاده مینماییم. براي ما، یک جمع میتواند درختی باشد با یک + در ریشـه، یـک ضـرب در سـمت چپ و یک جمع در سمت راست؛ یا میتواند تنها از یک ضرب تشکیل شده باشد. اگر مایلید با این تعریف کار کنید، لازم است بدانید که خصوصیت زیبـایی دارد: مـیتـوانیم هـر عبارتی را (بدون پرانتزها) بهعنوان مجموعی از حاصلضربها نمایش دهیم. این ویژگی اساس الگـوریتم تجزیۀ ما است. getSum سعی میکند درختی بسازد که یک ضرب سمت چپ آن و یک جمع سـمت راسـت آن باشد، اما اگر یک علامت + پیدا نکند، تنها حاصلضرب را تولید میکند:
def getSum(tokenList):
a = getProduct(tokenList)
if getToken(tokenList, ‘+’):
b = getSum(tokenList)
return Tree (‘+’, a, b)
else:
return a
بیایید آن را با عبارت 7 * 5 + 11 * 9 آزمایش کنیم:
>>> tokenList = [9, ‘*’, 11, ‘+’, 5, ‘*’, 7, ‘end’]
>>> tree = getSum(tokenList)
>>> printTreePostorder(tree)
9 11 * 5 7 * +
کار تقریباً تمام است، اما ما هنوز باید بر روي پرانتزها کارکنیم. در هر کجاي یک عبارت که یک عدد بتواند وجود داشته باشد، یک جمع کامل هم میتواند درون پرانتز قرار گیرد. مـا تنهـا نیـاز داریـم getNumber را طوري تغییر دهیم که زیر عبارتها را هم پوشش دهد:
def getNumber(tokenList):
if getToken(tokenList, ‘(‘):
x = getSum(tokenList) # get the subexpression
getToken(tokenList, ‘)’) # remove the closing parenthesis
return x
else:
x = tokenList[0]
if type(x) != type(0): return None
tokenList[0:1] = []
return Tree (x, None, None)
بیایید این کد را با عبارت 7) * 5 + 11 * (9 آزمایش کنیم:
>>> tokenList = [9, ‘*’, ‘(‘, 11, ‘+’, 5, ‘)’, ‘*’, 7, ‘end’]
>>> tree = getSum(tokenList)
>>> printTreePostorder(tree)
9 11 5 + 7 * *
تجزیه گر، با پرانتزها بهدرستی برخورد میکند؛ عمل جمع قبل از عمل ضرب صورت مـیگیـرد. در نسخۀ نهایی برنامه، بد نیست نامی به getNumber بدهیم که نقش جدید آن را بهتر توصیف کند.
برای اموزش های ویدیویی زبان پایتون به بستر ویدیو های اموزشی بروید
ثبت نام
با ایمیل خود وارد شویدورود
