الگوریتم محوطه تغییر جهت

خطای اسکریپتی: پودمان «AfC submission catcheck» وجود ندارد.

"این مقاله در حال ترجمه از ویکی انگلیسی است. لطفا حذف نشود."

در علوم کامپیوتر ، الگوریتم محوطه تغییر جهت (شانتینگ یارد) (shunting-yard) روشی برای تجزیه عبارات ریاضی مشخص شده در نشانه گذاری میانوندی است. این روش می تواند یک رشته نماد پسوند، که به عنوان نشانه گذاری لهستانی معکوس (RPN) نیز شناخته می شود، یا یک درخت نحو انتزاعی (AST) تولید کند. ^[۱] این الگوریتم توسط ادسخر دایکسترا اختراع شد و الگوریتم "محوطه تغییر جهت" نامگذاری شد؛ زیرا عملکرد آن شبیه به محوطه ای است که جهت قطارها در آن برعکس می شود. دایکسترا برای اولین بار الگوریتم محوطه تغییر جهت را در گزارش موسسه ملی تحقیقات ریاضی و علوم کامپیوتر (Centrum Wiskunde & Informatica) منتشر کرد.

همانند روش ارزیابی در نشانه گذاری لهستانی معکوس (RPN)، الگوریتم محوطه تغییر جهت بر پشته بنا نهاده شده است. عبارات میانوندی شکلی از نمادهای ریاضی هستند که اکثر مردم به آن عادت دارند و از آن استفاده می کنند، به عنوان مثال "3 + 4" یا "3 + 4 × (2 - 1)" . دو متغیر متنی(رشته) برای انجام تبدیل وجود دارد: ورودی و خروجی. همچنین یک پشته وجود دارد که اپراتورهایی را که هنوز به صف خروجی اضافه نشده اند، نگه می دارد. برای تبدیل، برنامه هر نماد را به ترتیب می خواند و بسته به آن نماد، کاری انجام می دهد. نتیجه مثال‌های بالا به ترتیب "3 4 +" و "3 4 2 1 - × +" بود. (در نشانه گذاری لهستانی معکوس )

الگوریتم محوطه تغییر جهت به درستی تمام عبارات میانوندی معتبر را تجزیه می کند، اما الزاما همه عبارات نامعتبر را رد نمی کند. به عنوان نمونه، "1 2 +" یک عبارت میانوندی معتبر نیست، اما الگوریتم آن را به عنوان "1 + 2" تجزیه می کند. با این حال، الگوریتم می‌تواند عباراتی را که دارای پرانتزهای ناهماهنگ هستند، رد کند.

الگوریتم محوطه تغییر جهت بعداً به تجزیه عملگر اولویت تعمیم داده شد. رده:ادسخر دیکسترا رده:اختراع‌های هلندی رده:الگوریتم‌های تجزیه

This article "الگوریتم محوطه تغییر جهت" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:الگوریتم محوطه تغییر جهت. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.