آموزش ساختمان داده قسمت ششم

1395/1/23 سعید ضیادید 2482

به نام خدا
سلام عرض می کنم خدمت همه ی شما دوستان عزیز .ضیادید هستم و در خدمت شما خواهم بود با جلسه ششم آموزش ساختمان داده ها از سری آموزش های برنامه نویسی
در این جلسه قصد داریم مبحث پشته و صف رو ادامه بدیم.

دراین جلسه سعی می کنیم درباره ی "ارزشیابی عبارات" صحبت کنیم . ببنید دوستان همونطور که میدونید در عبارتی مثل a*b ، دو عملوند (a,b) و یک عملگر (*) داریم . همچنین میتونیم بگیم که دو نوع عملگر داریم . 1- عملگر های یکانی 2- عملگر های باینری . عملگر های یکانی فقط به یک عملوند نیاز دارند مثل منفی و مثبت . اما عملگرهای باینری یا دودویی به دو عملوند نیاز دارند مثل جمع و تفریق و ضرب و تقسیم و توان . اولویت عملگر ها هم به صورت زیر هست :
1- پرانتز
2- عملگر های یکانی منفی و مثبت
3-توان
4- ضرب و تقسیم
5- جمع و تفریق

در قسمت 4و5 هم اگر چند عملگر هم اولویت داشته باشیم، اولویت از چپ به راست خواهد بود .

در زیر می تونید مثال هایی از اولویت بندی عبارات رو ملاحظه بفرمایید :

 

آموزش ساختما داده

 

ساختمان داده


 

آموزش ساختمان داده

 

آموزش ساختمان داده ها

 

ساختمان داده ها

اما در این مبحث ، موضوع دبگه ای که میتونه مهم باشه ، درخت عبارت محاسباتی یا همون درخت پارس هست . برای تشکیل هر درخت پارس به صورت زیر عمل می کنیم :
1-ابتدا عبارت رو برحسب اولویت عملگر هاش اولویت بندی می کنیم .
2-ریشه درخت ، کم اولویت ترین خواهد بود .
3-ریشه زیر درختان چپ و راست به ترتیب کم اولویت ترین عملگر از نظر اولویت در چپ و راست ریشه درخت هستند .
4-برگ های درخت ، عملوند ها هستند .

در زیر هم میتونید تعدادی مثال از درخت عبارت محاسباتی مشاهده بفرمایید.


 

ساختمان داده ها


 

ساختمان داده


 

ساختمان داده


اما دوستان ، عبارات از نظر نحوه ی قرار گیری عملگر ها به 3 دسته ی میانوندی ، پیشوندی و پسوندی تقسیم میشن .
عبارت میانوندی یا infix: در این نوع عبارت ، عملگر بین عملوندهاش قرار میگیره .مثلا عبارت a*b یک عبارت میانوندی هست .
 عبارت پسوندی هم عبارتی هست در اون عملگر بعد از عملوند هاش قرار میگیره . به روش پسوندی ، روش لهستانی معکوس هم گفته میشه .
در عبارت های پیشوندی هم عملگر ، قبل از عملوند هاش قرار میگیره . به این روش ، لهستانی هم میگن .

نکته ی مهم اینه که در تبدیل این 3 عبارت به همدیگه ، ترتیب عملوند ها تغییری نمیکنه . مثلا عبارت های زیر رو ببینید :

میانوندی     a+b*c
پیشوندی     abc*+
پسوندی      *+abc


همونطور که مشاهده می کنید ، در هر سه عبارت ترتیب عملوند ها (a,b,c) حفظ شدند .

برای ارزشیابی عبارت های پسوندی و پیشوندی و به دست آوردن مقدار نهایی ، به صورت زیر عمل می کنیم :
1-کنترل می کنیم که آیا تعداد عملوند ها یک واحد از عملگر ها بیشتر هست یا نه . چون در غیر این صورت در عبارت عملگر یکانی وجود داشته و ارزشیابی اون شرایط خاصی خواهد داشت .
2-عبارت رو از سمتی بررسی می کنیم که با عملوند شروع بشه .
3-با رسیدن به هر عملگر ، دو عملوند براش در نظر میگیریم .
4-با توجه به عملگر ، عملیات رو روی عملوند ها انجام میدیم .

برای تبدیل عبارت ها به یکدیگر هم 3 روش وجود داره که عبارت هستن از :
1-روش پرانتز گذاری
2-استفاده از پشته
3-پیمایش درخت پارس

ما انشاءالله دو روش اول رو برای تبدیل عبارت های پسوندی و پیشوندی به میانوندی و برعکس ، در جلسه ی بعدی توضیح خواهیم داد و تا حدی درباره ی صف حلقوی نکاتی رو عرض خواهیم کرد . همچنین در جلسه ی بعدی ، مقدمات مبحث "لیست پیوندی " رو مطرح خواهیم کرد.

با تشکر از همه ی شما دوستان عزیز . خدانگهدار