وبلاگ رسمی مهدی غلامی میاندهی

الگوریتم هایی برای تبدیل عبارت های میانوندی ، پسوندی و پیشوندی به یکدیگر

1- تبدیل عبارت میانوندی به پسوندی

الگوریتمی را که در زیر می بینید برای تبدیل یک عبارت میانوندی به یک عبارت پسوندی به کمک پشته و به زبان  C++نوشته شده است . این برنامه به این صورت عمل می کند که ابتدا عبارت را پرانتز گذاری می کند و سپس از سمت چپ به راست شروع به پردازش رشته می کند و اپرندها(عملوند) را به خروجی می فرستد اما اپراتورها(عملگر) و پرانتز باز را وارد پشته می کند . اما اگر اپراتوری را وارد پشته نمود اما اپراتوری با اولویت بالاتر یا هم اولویت با آن در پشته قرار داشت ، ابتدا آن اپراتور را از پشته خارج می کند . اگر به پرانتز بسته رسیدیم تمام اپراتورهای تا اولین پرانتز باز را از پشته خارج می کند .

در الگوریتم زیر isp اولویت در پشته و icp اولویت ورودی را نشان می دهند . # نیز نماینده سمت چپ ترین نشانه می باشد . e معرف رشته ای است که آن را پردازش می کنیم و x وy هم نشانه ها و یا لیترال ها می باشند.

Void postfix (exp e)

{

Stackstack;

Token y;

Stack.Add ("#");

For (token x=NextToken (e); x! ="#"; x=NextToken (e))

{

If(x is an operand)

Cout<

Else if (x= = ")")

For (y=*stack.Delete(y); y! ="("; y=*stack.Delete(y))     

Cout << y;     

//x is an operator

Else

{

For(y=*stack.Delete(y); ISP(y) <=icp(x); y=*stack.Delete(y))

Cout<

Stack.Add(y);

Stack.Add(x);

}

}

While (! stack.isEmpty ())

Cout<<*stack.Delete(y);

}

سایر الگوریتم ها نیز به همین ترتیب به دست می آیند .  

تبدیلات زیر را در نظر بگیرید :

Infix :(     (     (     (   A   *    B    )    /     C     )    -    D    )   +     E      )

Post:  (     (     (     (   A   B    *    )   C     /      )   D    -     )   E     +      )

Pre :  (     +    (      -   (    /      (    *   A    B     )   C    )     D   )     E      )

2- تبدیل عبارت پسوندی به پیشوندی:

الف) روش مستقیم :عبارت پسوندی را از چپ به راست به صورت (عملگر  -   عملوند   -   عملوند) پرانتز گذاری کرده و سپس عملگر را به قبل از پرانتز باز آن عبارت منتقل می کنیم .

ب) ابتدا آن را به فرم میانوندی تبدیل نموده و سپس از میانوندی به پیشوندی می بریم . برای نوشتن الگوریتم ، این روش ساده تر است .

3- تبدیل عبارت پیشوندی به پسوندی:

الف ) روش مستقیم : عبارت پسوندی را از راست به چپ به صورت (عملوند -  عملوند  -   عملگر  ) پرانتز گذاری کرده و سپس عملگر را به بعد از پرانتز بسته آن عبارت منتقل می کنیم .

ب) ابتدا آن را به فرم میانوندی برده و سپس از میانوندی به پسوندی تبدیل می کنیم . برای نوشتن الگوریتم ، این روش ساده تر است .

4- تبدیل عبارت پسوندی به میانوندی

از یک پشته استفاده می کنیم . از چپ به راست عبارت را ارزیابی نموده و عملگرها را در پشته قرار می دهیم و اگر به عملوندی رسیدیم آن را بر دو عبارت بالای پشته اعمال کرده و نتیجه را در پشته قرار می دهیم . ( دقت کنید که پایینی بر بالایی اعمال می شود . )

5- تبدیل عبارت پیشوندی به میانوندی

از یک پشته استفاده می کنیم . از راست به چپ عبارت را ارزیابی نموده و عملگرها را در پشته قرار می دهیم و اگر به عملوندی رسیدیم آن را بر دو عبارت بالای پشته اعمال کرده و نتیجه را در پشته قرار می دهیم . ( دقت کنید که عملوند بالایی بر عملوند پایینی اعمال می شود . )

6- تبدیل عبارت میانوندی به پیشوندی

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

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