From Wikipedia, the free encyclopedia
نشانهگذاری لهستانی معکوس (به انگلیسی: Reverse Polish notation) یا نشانهگذاری پسوندی (به انگلیسی: postfix notation) یک روش نشانهگذاری عبارت محاسباتی، منطقی و جبری است که در آن هر عملگر مابعد عملوندهای خود نوشته میشود. به عنوان مثال، عبارت زیر یک عبارت پسوندی است:
۲ ۳ +
که در آن عملگر + مابعد عملوندهای خود (۲ و ۳) نوشته شدهاست.
برای تبدیل یک عبارت میانوندی به پسوندی میتوان از روش زیر استفاده کرد:[1]
الگوریتم ارزیابی عبارات پسوندی بسیار سرراست است:
فرض کنید میخواهیم عبارت میانوندی زیر را با استفاده از الگوریتم بالا ارزیابی کنیم:
۵ + ((۱ + ۲) * ۴) − ۳
ابتدا این عبارت را به صورت لهستانی معکوس نشانهگذاری میکنیم:
۵ ۱ ۲ + ۴ * + ۳ -
عبارت از چپ به راست و با استفاده از الگوریتم بالا ارزیابی میشود:
ورودی | عملیات | پشته | توضیحات |
---|---|---|---|
۵ | گذاشتن مقدار در پشته | ۵ | |
۱ | گذاشتن مقدار در پشته | ۱ ۵ | |
۲ | گذاشتن مقدار در پشته | ۲ ۱ ۵ | |
+ | جمع | ۳ ۵ | برداشتن دو مقدار (۱, ۲) از پشته و قرار دادن نتیجه عملیات (۳) در پشته |
۴ | گذاشتن مقدار در پشته | ۴ ۳ ۵ | |
* | ضرب | ۱۲ ۵ | برداشتن دو مقدار (۳, ۴) از پشته و گذاشتن نتیجه عملیات (۱۲) در پشته |
+ | جمع | ۱۷ | برداشتن دو مقدار (۵, ۱۲) از پشته و قرار دادن نتیجه عملیات (۱۷) در پشته |
۳ | گذاشتن مقدار در پشته | ۳ ۱۷ | |
− | تفریق | ۱۴ | برداشتن دو مقدار (۱۷, ۳) از پشته و قرار دادن نتیجه عملیات (۱۴) در پشته |
نتیجه | (۱۴) |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.