نشانه‌گذاری لهستانی معکوس
نشانه‌گذاری لهستانی معکوس (به انگلیسی: Reverse Polish notation) یا نشانه‌گذاری پسوندی (به انگلیسی: postfix notation) یک روش نشانه‌گذاری عبارت محاسباتی، منطقی و جبری است که در آن هر عملگر مابعد عملوندهای خود نوشته می‌شود. به عنوان مثال، عبارت زیر یک عبارت پسوندی است:
۲ ۳ +
که در آن عملگر + مابعد عملوندهای خود (۲ و ۳) نوشته شده‌است.
تبدیل از عبارت میانوندی به پسوندی
برای تبدیل یک عبارت میانوندی به پسوندی می‌توان از روش زیر استفاده کرد:[1]
- ابتدا عبارت را به‌طور کامل پرانتزگذاری می‌کنیم. (بنا بر اولویت عملگرها)
- هر عملگر را به سمت راست پرانتز بسته خود منتقل می‌کنیم.
- تمام پرانتزها را حذف می‌کنیم.
الگوریتم پسوندی
الگوریتم ارزیابی عبارات پسوندی بسیار سرراست است:
- تا زمانی که هنوز نشانه‌ای وجود دارد،
- نشانه بعدی را از ورودی دریافت کن.
- اگر نشانه یک عملوند (مقدار) بود،
- آن را پشته قرار بده.
- در غیر این صورت، نشانه یک عملگر است. (عملگر هم در اینجا هم به معنی عملگر ریاضی و هم توابع است)
- این یک انی است که عملگر n آرگومان دریافت می‌کند.
- اگر کمتر از n مقدار در پشته وجود دارد.
- (خطا) کاربر به اندازه کافی عملوند (مقدار) وارد نکرده است.
- وگرنه، n مقدار بالای پشته را بردارید.
- عملگر را با استفاده از مقادیر ارزیابی کنید.
- نتیجه عملیات را در پشته قرار دهید.
- اگر در پشته فقط یک مقدار وجود دارد،
- آن مقدار نتیجه عملیات است.
- اگر بیش از یک مقدار در پشته وجود دارد،
- (خطا) کاربر عملوندهای زیادی وارد کرده‌است.
مثال
فرض کنید می‌خواهیم عبارت میانوندی زیر را با استفاده از الگوریتم بالا ارزیابی کنیم:
۵ + ((۱ + ۲) * ۴) − ۳
ابتدا این عبارت را به صورت لهستانی معکوس نشانه‌گذاری می‌کنیم:
۵ ۱ ۲ + ۴ * + ۳ -
عبارت از چپ به راست و با استفاده از الگوریتم بالا ارزیابی می‌شود:
| ورودی | عملیات | پشته | توضیحات |
|---|---|---|---|
| ۵ | گذاشتن مقدار در پشته | ۵ | |
| ۱ | گذاشتن مقدار در پشته | ۱ ۵ | |
| ۲ | گذاشتن مقدار در پشته | ۲ ۱ ۵ | |
| + | جمع | ۳ ۵ | برداشتن دو مقدار (۱, ۲) از پشته و قرار دادن نتیجه عملیات (۳) در پشته |
| ۴ | گذاشتن مقدار در پشته | ۴ ۳ ۵ | |
| * | ضرب | ۱۲ ۵ | برداشتن دو مقدار (۳, ۴) از پشته و گذاشتن نتیجه عملیات (۱۲) در پشته |
| + | جمع | ۱۷ | برداشتن دو مقدار (۵, ۱۲) از پشته و قرار دادن نتیجه عملیات (۱۷) در پشته |
| ۳ | گذاشتن مقدار در پشته | ۳ ۱۷ | |
| − | تفریق | ۱۴ | برداشتن دو مقدار (۱۷, ۳) از پشته و قرار دادن نتیجه عملیات (۱۴) در پشته |
| نتیجه | (۱۴) |
جستارهای وابسته
منابع
- ساختمان داده‌ها به زبان سی، نوشته الیس هورویتز، ترجمه امیر علیخانزاده، انتشارات خراسان، صفحه ۱۳۴
مشارکت‌کنندگان ویکی‌پدیا. «Reverse Polish notation». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۱۴ ژوئیه ۲۰۱۳.