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

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

۲ ۳ +

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

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

ویرایش

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

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

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

ویرایش

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

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

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

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

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

۵ ۱ ۲ + ۴ * + ۳ -

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

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

جستارهای وابسته

ویرایش

منابع

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

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