پرش به محتوا

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

از ویکی‌پدیا، دانشنامهٔ آزاد

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

۲ ۳ +

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

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

[ویرایش]

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

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

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

[ویرایش]

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

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

مثال

[ویرایش]

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

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

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

۵ ۱ ۲ + ۴ * + ۳ -

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

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

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

[ویرایش]

منابع

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

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