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

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

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

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

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

مثال

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

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

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

• نشانه‌گذاری میانوندی
• نشانه‌گذاری لهستانی
• پشته

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