الگوریتم تبدیل infix یک عبارت محاسبایی به postfix و prefix

 

 

فرض کنید عبارت زیر را دارید :

((a+b)*(c-d))/(e-f)

عبارت بالا یک عبارت infix (میان ترتیب) است زیرا عملگر بین عملوند هایش آمده است ، به طور مثال در عبارت بالا ” – ” بین c و d آمده است.

در این پست عباراتی را که بررسی می کنیم شامل عملگرهای + , – , / , * و پرانتز است. اولویت این عملگرها به ترتیب زیر است:

  1. * ، /
  2. – ، +

و این عملگرها شرکت پذیری از سمت چپ به راست دارند.

 

درخت عبارت بالا به شکل زیر می شود:

infix to postfix prefix

اگر عبارت بالا را به صورت inorder پیمایش کنیم یعنی ابتدا ریشه را ببینیم بعد فرزند چپ و بعد فرزند راست، دقیقا عبارت بالا بدون پرانتز به دست می آید که همان شکل infix است:

 

a + b * c – d / e – f

prefix (پیش ترتیب) یک عبارت محاسباتی یعنی عملگر قبل از عملوند هایش بیاید،برای اینکه شکل prefix عبارت بالا را به دست بیاوریم باید درخت بالا به صورت preorder پیمایش کنیم یعنی ابتدا ریشه را ببینیم بعد فرزند چپ و بعد فرزند راست که عبارت زیر به دست می آید:

 

/ * + a b – c d – e f

postfix (پس ترتیب) یک عبارت محاسباتی یعنی عملگر بعد از عملوندهایش بیاید، که می توان شکل postfix یک عبارت محاسباتی را از روی درختش با استفاده از پیمایش postorder با کمی تغییر به دست آورد.
در پیمایش postorder ابتدا فرزند چپ و بعد فرزند راست و بعد ریشه را می بینیم ولی باید در این الگوریتم کمی تغییر ایجاد کنیم، و آن این است که به جای اینکه ابتدا فززند چپ و بعد راست و بعد ریشه را ببینیم ، ایتدا فرزند راست و بعد فرزند چپ و بعد ریشه را ببینیم که عبارت زیر به دست می آید:

 

f e – d c – b a + * /

  روش هایی که در بالا  گفتیم به صورت بازگشتی از روی درخت عبارت محاسباتی شکل های infix ، postfix و prefix یک عبارت محاسباتی را حساب می کند.

ولی می توان به صورت مستقیم نمایش prefix و postfix یک عبارت محاسباتی را از روی نمایش infix آن عبارت با استفاده از یک stack (پشته) به دست آورد.

به دست آوردن نمایش postfix از روی نمایش infix با استفاده از stack :

ابتدا از سمت راست شروع به خواندن تک تک اجزای عبارت محاسباتی می کنیم ،که به صورت infix است و به سمت چپ حرکت می کنیم.

یک استک را برای نگه داری عملگرهای در نظر می گیریم. اگر جزیی را که از عبارت خوانده ایم یک عدد یا متغییر است (عملوند) آن را به صورت مستقیم در خروجی چاپ می کنیم. اگر عملگر یا پرانتز بود کار های زیر را انجام می دهیم:

  1. اگر پرانتز بسته ” (” بود آن را در استک push  می کنیم.
  2. اگر پرانتز باز “)” بود تا زمانی در استک به پرانتز بسته برسیم pop می کنیم و در سر راه هرچه عملگر دیدیم آن را در خروجی چاپ می کنیم.
  3. اگر یک عملگر بود و در سر استک پرانتز بسته “(” بود عملگر را در استک push  می کنیم.
  4. اگر عملگر بود و در سر استک یک عملگر دیگر موجود بود دو حال وجود دارد اگر عملگری که دیدیدم از عملگری که در سر استک است، اولویت کمتری داشت عملگر سر استک را از استک pop می کنیم و آن را در خروجی چاپ می کنیم  و دوباره چک می کنیم آیا عملگری که دیده ایم با چیزی که سر استک هست اولویتش کمتر است یا نه اگر کمتر بود دوباره همین کار را می کنیم تا زمانی که اولویتش کمتر از عملگر سر استک نباشد و بعد عملگری را که دیده ایم در استک push می کنیم، حالت دوم زمانی اتفاق می افتد که عملگری را که دیده ایم اولویت بیشتری از عملگر سر استک برخوردار باشد در این صورت عملگر جدیدی را که دیده ایم در استک push می کنیم.

اگر تک تک اجزای عبارت را از سمت راست به چپ را دیدیم ولی استک خالی نشده بود تمام محتویات استک را تا زمانی که خالی شود pop می کنیم و عملگرها را در خروجی نمایش می دهیم.

مراحل بالا را برای عبارت داده شده را در زیر می بینید:

 

infix to prefix

همین طور که نمایش postfix عبارت ابتدای متن 

f e – d c – b a + * /

می شود که برابر با postfix است که با پیمایش درخت به دست آوردیم.

به دست آوردن نمایش prefix از روی نمایش infix با استفاده از stack :

دقیقا مانند مرحله ی قبل عمل می کنیم و نمایش postfix را به دست می آوریم سپس خروجی را برعکس می کنیم و نمایش prefix به دست می آید:

f e – d c – b a + * /

–>

/ * + a b – c d – e f

بعدا کد سی پلاس پلاس و جاوااسکریپ الگوریتم های گفته شده را به پست اضافه می کنم.

Digg This
Reddit This
Stumble Now!
Buzz This
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Kick It on DotNetKicks.com
Shout it
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)

۶ دیدگاه

  • ببخشید یه سوال
    راه خوبی عه اگر برای محاسبه عبارتی که sin cos اینا داشته باشه از این روش بریم؟

    • برای هر چیزی که ترتیبش از چپ به راست باشد می شود ولی چیزی مثل توان را نمی توان با این حساب کرد – اون موقع باید رفت سراغ مباحث توی کامپایلر – چیزهایی مثل LR , LL

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

  • خیلی خوب بود. ممنون از آموزش هایِ حرفه ای و کارامدتون.. خسته نباشید ♥

  • مرسی عالی بود:)

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *