سوال در ارتباط با مبحث ارزیابی عبارت ها

[Iron_Fist]

با سلام به دوستان

من یه عبارت Infix دارم و می خواهم به عبارت Prefix تبدیلش کنم
عبارت Infix این هست :                 A+B)*(C+D)-(E/F)+H)
حالا توش موندم جواب درست کدوم یک از جواب های زیر هست
       AB+CD/EFH+*- +       یا           AB+CD+/EFH+*-

با تشکر

[Mamad2003]

سلام . عبارت دومی عبارت درست هست !

[Iron_Fist]

ممد جان سلام
خسته نباشی

یعنی علویت عملگر با این حساب تو تبدیل Infix به Prefix از سمت
راست به چپ هست
ممد جون حقیقتش قضیه اینه که این استاد دانشگاه ما کلید کرده
که یه الگوریتمی بنویسیم که نتیجه اول رو بده
یعنی اولویت عملگر از چپ به راست باشه
من خودمم چند جا دیدم از چپ به راست حساب کرده و چند جا هم
از راست به چپ
یعنی ممکنه جفتش درست باشه

پیشاپیش از کمک متشکرم

[Mamad2003]

خسرو جان سلام
من یه بررسی کردم دیدم که یه الگوریتم هست برای ساخت عبارت prefix ، بجای یک پشته از دو پشته استفاده می کنه ! توی این الگوریتم تقدم عملگر ها در نظر گرفته نمیشن :

1- دو تا پشته در نظر میگیریم .
2- نماد های عبارت infix رو از آخر به اول بررسی می کنیم بشکل زیر :

1) اگر نماد پرانتز بسته یا عملگر بود اونو توی پشته شماره 1 میزاریم
2) اگر نماد عملوند بود در پشته شماره 2 قرار میدیم
3) اگر نماد پرانتز باز بود ، از پشته 1 دوتا نماد برمیداریم . هر کدوم از اونها که عملگر بود به پشته دوم اضافه می کنیم .


3-این عمل رو تا جایی که به اول عبارت infix برسیم تکرار می کنیم .
4- در پایان مقدار موجود در پشته دوم رو معکوس می کنیم . در این زمان به جواب prefix می رسیم .

[Iron_Fist]

ممد جان سلام

ممکنه جواب های روش های مختلف با هم فرق بکنه
یا اصلآ یه عبارت Infix می تونه چند تا Prefix داشته باشه ؟

با تشکر

[Iron_Fist]

ممد جان فکر کنم این تاپیک رو یادت رفته
نه ؟

[Darg]

خسرو جان میشه یکمی (محدود) درباره Prefix و InFix توضیح بدی.
آخه من حتی نفهمیدم درباره چی داره اینجا بحث می شه...

[Mamad2003]

ممد جان سلام

ممکنه جواب های روش های مختلف با هم فرق بکنه
یا اصلآ یه عبارت Infix می تونه چند تا Prefix داشته باشه ؟

با تشکر

سلام
والا این که جواب ها بخواد فرق بکنه یه حالت داره و اونم اینه که تقدم ( Priority ) یا جهت محاسبه ( Associativity ) عملگر ها رو تغییر بدیم وگرنه نباید جواب های مختلف بگیریم !

[Iron_Fist]

والا این که جواب ها بخواد فرق بکنه یه حالت داره و اونم اینه که تقدم ( Priority ) یا جهت محاسبه ( Associativity ) عملگر ها رو تغییر بدیم وگرنه نباید جواب های مختلف بگیریم

ممد جان سلام

صحبت من هم از اول همین بود
ببین اگه ما الویت عملگرمون ( تقدم عملگر ) از راست به چپ باشه چواب دوم درسته
و اگه الویت عملگرمون از چپ به راست باشه جواب اول صحیحه
در ضمن تو این لینکی که من دادم طرف الویت عملگر رو اومده
از چپ به راست حساب کرده یعنی با روش ایشون جواب اول
درسته
فکر کنم بشه این نتیجه رو گرفت که دو جواب صحیح هستند
http://www.cs.man.ac.uk/~pjj/cs2121/fix.html

خسرو جان میشه یکمی (محدود) درباره Prefix و InFix توضیح بدی.
آخه من حتی نفهمیدم درباره چی داره اینجا بحث می شه...

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

[Mamad2003]

صحبت من هم از اول همین بود
ببین اگه ما الویت عملگرمون ( تقدم عملگر ) از راست به چپ باشه چواب دوم درسته
و اگه الویت عملگرمون از چپ به راست باشه جواب اول صحیحه
در ضمن تو این لینکی که من دادم طرف الویت عملگر رو اومده
از چپ به راست حساب کرده یعنی با روش ایشون جواب اول
درسته
فکر کنم بشه این نتیجه رو گرفت که دو جواب صحیح هستند
http://www.cs.man.ac.uk/~pjj/cs2121/fix.html

کاملا درسته ! زمانی که الویت از چپ به راست باشه جواب اول درسته ! زمانی که الویت هم از راست به چپ باشه دومی درسته !
خب فکر کنم به جوابت رسیدی . این بستگی به خواسته طراح الگوریتم داره . مثلا توی همه کامپایلر ها عملگر های - + / * به اصطلاح Left Associative هستند یعنی الویت اونها از چپ به راسته .
پس اگه مثلا این عبارتی که شما نوشتی بخواد توی کامپایلر ++C/C بررسی و parse بشه ، با توجه به Left Associative بودن عملگر ها ، کامپایلر جواب اول رو تولید میکنه !
پس این نکته قابل ذکر هست که درست بودن یا نبودنش بستگی به موقعیتش داره . درسته که این عملگر ها Left Associative هستند ولی اگر همین + یا - بشکل تکی یا Unary ( نشانه مثبت بودن یا منفی بودن عدد یا عبارت مثلا 2- ) استفاده بشن اونوقت خاصیت Right Associative پیدا می کنند . اونوقته که کامپایلر جهت گیری متفاوتی داره . قضیه به همین سادگی ها نیست حالا میتونه ترکیبی از اینها وجود داشته باشه که اونوقت باید یه الگوریتم خیلی کامل تر از این بیاد و عبارت رو کنترل کنه .
کلا این بحث postfix و infix که توی کتاب های ساختمان داده میشه خیلی ابتدایی و ساده هستند و خیلی کاربردی نیستند . کاربرد اصلی اونها در ساخت بخش parser کامپایلر هست !

[Iron_Fist]

ممد جان خیلی ممنون از اینکه وقتت رو به مادادی
متشکرم