نشانه‌گذاری لهستانی معکوس

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

نشانه‌گذاری لهستانی معکوس (به انگلیسی: Reverse Polish notation) یا نشانه‌گذاری پسوندی (به انگلیسی: postfix notation) یک روش نشانه‌گذاری عبارت محاسباتی، منظقی و جبری است که در آن هر عملگر مابعد عملوندهای خود نوشته می‌شود. به عنوان مثال، عبارت زیر یک عبارت پسوندی است:

۲ ۳ +

که در آن عملگر + مابعد عملوندهای خود (۲ و ۳) نوشته شده است.

تبدیل از عبارت میانوندی به پسوندی[ویرایش]

برای تبدیل یک عبارت میانوندی به پسوندی می‌توان از روش زیر استفاده کرد:[۱]

  • ابتدا عبارت را به طور کامل پرانتز گذاری می‌کنیم. (بنا بر اولویت عملگرها)
  • هر عملگر را به سمت راست پرانتز بسته خود منتقل می‌کنیم.
  • تمام پرانتزها را حذف می‌کنیم.

الگوریتم پسوندی[ویرایش]

الگوریتم ارزیابی عبارات پسوندی بسیار سرراست است:

  • تا زمانی که هنوز نشانه‌ای وجود دارد،
    • نشانه بعدی را از ورودی دریافت کن.
    • اگر نشانه یک عملوند (مقدار) بود،
    • در غیر این صورت، نشانه یک عملگر است. (عملگر هم در اینجا هم به معنی عملگر ریاضی و هم توابع است)
      • این یک انی است که عملگر n آرگومان دریافت می‌کند.
      • اگر کمتر از n مقدار در پشته وجود دارد.
        • (خطا) کاربر به اندازه کافی عملوند (مقدار) وارد نکرده است.
      • وگرنه، n مقدار بالای پشته را بردارید.
      • عملگر را با استفاده از مقادیر ارزیابی کنید.
      • نتیجه عملیات را در پشته قرار دهید.
  • اگر در پشته فقط یک مقدار وجود دارد،
    • آن مقدار نتیجه عملیات است.
  • اگر بیش از یک مقدار در پشته وجود دارد،
    • (خطا) کاربر عملوندهای زیادی وارد کرده است.

مثال[ویرایش]

فرض کنید می‌خواهیم عبارت میانوندی زیر را با استفاده از الگوریتم بالا ارزیابی کنیم:

۵ + ((۱ + ۲) * ۴) − ۳

ابتدا این عبارت را به صورت لهستانی معکوس نشانه‌گذاری می‌کنیم:

۵ ۱ ۲ + ۴ * + ۳ -

عبارت از چپ به راست و با استفاده از الگوریتم بالا ارزیابی می‌شود:

ورودی عملیات پشته توضیحات
۵ گذاشتن مقدار در پشته ۵
۱ گذاشتن مقدار در پشته ۱
۵
۲ گذاشتن مقدار در پشته ۲
۱
۵
+ جمع ۳
۵
برداشتن دو مقدار (۱, ۲) از پشته و قرار دادن نتیجه عملیات (۳) در پشته
۴ گذاشتن مقدار در پشته ۴
۳
۵
* ضرب ۱۲
۵
برداشتن دو مقدار (۳, ۴) از پشته و گذاشتن نتیجه عملیات (۱۲) در پشته
+ جمع ۱۷ برداشتن دو مقدار (۵, ۱۲) از پشته و قرار دادن نتیجه عملیات (۱۷) در پشته
۳ گذاشتن مقدار در پشته ۳
۱۷
تفریق ۱۴ برداشتن دو مقدار (۱۷, ۳) از پشته و قرار دادن نتیجه عملیات (۱۴) در پشته
نتیجه (۱۴)

جستارهای وابسته[ویرایش]

منابع[ویرایش]

  1. ساختمان داده‌ها به زبان سی، نوشته الیس هوریتز، ترجمه امیر علیخانزاده، انتشارات خراسان، صفحه ۱۳۴

مشارکت‌کنندگان ویکی‌پدیا، «Reverse Polish notation»، ویکی‌پدیای en، دانشنامهٔ آزاد (بازیابی در ۱۴ ژوئیه ۲۰۱۳).