الگوریتم محوطه تعویض خط

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

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

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

الگوریتم محوطه تغییر جهت بعداً به تجزیه عملگر اولویت تعمیم داده شد.

یک تبدیل ساده

1. ورودی: 3 + 4
2. 3 را به صف خروجی وارد کنید. (هرگاه عددی خوانده شد، به خروجی وارد شود.)
3. + (یا ID آن را) بر روی پشته عملگرها وارد کنید.
4. 4 را به صف خروجی وارد کنید.
5. پس از خواندن عبارت، عملگرها را از پشته خارج کنید و آن ها را به خروجی اضافه کنید.

   در این مثال، فقط یک "+" وجود دارد.

6. خروجی: 3 4 +

این تبدیل ساده، چند قانون را نشان می‌دهد:

• همه اعداد هنگام خوانده شدن به وارد صف خروجی می‌شوند.
• در پایان خواندن عبارت، همه عملگرها را از پشته خارج کرده و روی خروجی قرار دهید.

نمایش گرافیکی الگوریتم

در تصویر فوق، نمایش گرافیکی الگوریتم را با استفاده از تقاطع سه طرفه راه آهن مشاهده می کنید. در هر مرتبه، یک نماد از ورودی پردازش می‌شود: اگر یک متغیر یا عدد پیدا شود، مستقیماً در خروجی کپی می‌شود (مراحل a، c، e ،h). اگر آن نماد یک عملگر باشد، روی پشته عملگر وارد می شود (مراحل b، d، f). اگر تقدم عملگر جدید کمتر از عملگر بالای پشته باشد یا تقدم آنها با هم برابر باشند و عملگر شرکت پذیر چپ باشد، آن عملگر از پشته خارج شده و به خروجی اضافه می‌شود (مرحله g). نهایتا هر عملگر باقی مانده از پشته خارج می شود و به خروجی اضافه می شود (مرحله i).

الگوریتم با جزئیات

 

/* This implementation does not implement composite functions, functions with variable number of arguments, and unary operators. */ while there are tokens to be read: read a token if the token is: - a number: put it into the output queue - a function: push it onto the operator stack - an operator o1: while ( there is an operator o2 other than the left parenthesis at the top of the operator stack, and (o2 has greater precedence than o1 or they have the same precedence and o1 is left-associative) ): pop o2 from the operator stack into the output queue push o1 onto the operator stack - a left parenthesis (i.e. "("): push it onto the operator stack - a right parenthesis (i.e. ")"): while the operator at the top of the operator stack is not a left parenthesis: {assert the operator stack is not empty} /* If the stack runs out without finding a left parenthesis, then there are mismatched parentheses. */ pop the operator from the operator stack into the output queue {assert there is a left parenthesis at the top of the operator stack} pop the left parenthesis from the operator stack and discard it if there is a function token at the top of the operator stack, then: pop the function from the operator stack into the output queue /* After the while loop, pop the remaining items from the operator stack into the output queue. */ while there are tokens on the operator stack: /* If the operator token on the top of the stack is a parenthesis, then there are mismatched parentheses. */ {assert the operator on top of the stack is not a (left) parenthesis} pop the operator from the operator stack onto the output queue/* This implementation does not implement composite functions, functions with variable number of arguments, and unary operators. */

while there are tokens to be read:
    read a token
    if the token is:
    - a number:
        put it into the output queue
    - a function:
        push it onto the operator stack 
    - an operator o1:
        while (
            there is an operator o2 other than the left parenthesis at the top
            of the operator stack, and (o2 has greater precedence than o1
            or they have the same precedence and o1 is left-associative)
        ):
            pop o2 from the operator stack into the output queue
        push o1 onto the operator stack
    - a left parenthesis (i.e. "("):
        push it onto the operator stack
    - a right parenthesis (i.e. ")"):
        while the operator at the top of the operator stack is not a left parenthesis:
            {assert the operator stack is not empty}
            /* If the stack runs out without finding a left parenthesis, then there are mismatched parentheses. */
            pop the operator from the operator stack into the output queue
        {assert there is a left parenthesis at the top of the operator stack}
        pop the left parenthesis from the operator stack and discard it
        if there is a function token at the top of the operator stack, then:
            pop the function from the operator stack into the output queue
/* After the while loop, pop the remaining items from the operator stack into the output queue. */
while there are tokens on the operator stack:
    /* If the operator token on the top of the stack is a parenthesis, then there are mismatched parentheses. */
    {assert the operator on top of the stack is not a (left) parenthesis}
    pop the operator from the operator stack onto the output queue

برای تحلیل پیچیدگی زمان اجرای این الگوریتم، فقط باید توجه داشت که هر نشانه دقیقا یک بار خوانده می شود، هر عدد، تابع یا عملگر دقیقا یک بار چاپ می شود و هر تابع، عملگر یا پرانتز دقیقا یک بار وارد پشته می شود و یک بار از پشته خارج می شود - بنابراین، در بیشترین حالت هم تعداد ثابتی از عملیات به ازای هر نشانه (token) اجرا می شود، و بنابراین زمان اجرا O( n ) است - از نظر اندازه ورودی خطی است.

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

مثال با جزئیات

ورودی: 3 + 4 × 2 ÷ ( 1 - 5 ) ^ 2 ^ 3

عملگر	اولویت	شرکت پذیری
^	4	راست
×	3	چپ
÷	3	چپ
+	2	چپ
−	2	چپ

نماد ^ نشان دهنده عملگر توان می باشد.

نشانه	عملیات	خروجی	پشته عملگرها	یادداشت
3	نشانه را به خروجی اضافه کن	3
+	نشانه را وارد پشته کن	3	+
4	نشانه را به خروجی اضافه کن	3 4	+
×	نشانه را وارد پشته کن	3 4	× +	× اولویت بشتری از + دارد
2	نشانه را به خروجی اضافه کن	3 4 2	× +
÷	آخرین ورودی پشته را وارد خروجی کن	3 4 2 ×	+	÷ و × اولویت یکسانی دارند
	نشانه را وارد پشته کن	3 4 2 ×	÷ +	÷ اولویت بیشتری از + دارد
)	نشانه را وارد پشته کن	3 4 2 ×	( ÷ +
1	نشانه را به خروجی اضافه کن	3 4 2 × 1	( ÷ +
−	نشانه را وارد پشته کن	3 4 2 × 1	- ( ÷ +
5	نشانه را به خروجی اضافه کن	3 4 2 × 1 5	- ( ÷ +
(	آخرین ورودی پشته را وارد خروجی کن	3 4 2 × 1 5 -	( ÷ +	تکرار می شود تا زمانی که ")" پیدا شود
	آخرین ورودی را از پشته خارج کن	3 4 2 × 1 5 -	÷ +	پرانتز مطابق کنار گذاشته می شود
^	نشانه را وارد پشته کن	3 4 2 × 1 5 -	^ ÷ +	^ اولویت بشتری از ÷ دارد
2	نشانه را به خروجی اضافه کن	3 4 2 × 1 5 - 2	^ ÷ +
^	نشانه را وارد پشته کن	3 4 2 × 1 5 - 2	^ ^ ÷ +	^ راست به چپ تعیین می شود
3	نشانه را به خروجی اضافه کن	3 4 2 × 1 5 - 2 3	^ ^ ÷ +
پایان	تمام پشته را وارد خروجی کن	3 4 2 × 1 5 - 2 3 ^ ^ ÷ +

ورودی: sin ( max ( 2, 3 ) ÷ 3 × $\pi$ )

نشانه	عملیات	خروجی	پشته عملگرها	یادداشت
sin	نشانه را وارد پشته کن		sin
)	نشانه را وارد پشته کن		( sin
max	نشانه را وارد پشته کن		max ( sin
)	نشانه را وارد پشته کن		( max ( sin
2	نشانه را به خروجی اضافه کن	2	( max ( sin
,	چشم پوشی کن	2	( max ( sin
3	نشانه را به خروجی اضافه کن	2 3	( max ( sin
(	آخرین ورودی پشته را وارد خروجی کن	2 3	( max ( sin	تا زمانی که "(" بالای پشته است، تکرار شود
آخرین ورودی را از پشته خارج کن	2 3	max ( sin	پرانتز مطابق کنار گذاشته می شود
÷	آخرین ورودی پشته را وارد خروجی کن	2 3 max	( sin
	نشانه را وارد پشته کن	2 3 max	÷ ( sin
3	نشانه را به خروجی اضافه کن	2 3 max 3	÷ ( sin
×	آخرین ورودی پشته را وارد خروجی کن	2 3 max 3 ÷	( sin
	نشانه را وارد پشته کن	2 3 max 3 ÷	× ( sin
$\pi$	نشانه را به خروجی اضافه کن	2 3 max 3 ÷ $\pi$	× ( sin
(	آخرین ورودی پشته را وارد خروجی کن	2 3 max 3 ÷ $\pi$ ×	( sin	تا زمانی که "(" بالای پشته است، تکرار شود
	آخرین ورودی را از پشته خارج کن	2 3 max 3 ÷ $\pi$ ×	sin	پرانتز مطابق کنار گذاشته می شود
پایان	تمام پشته را وارد خروجی کن	2 3 max 3 ÷ $\pi$ × sin

همچنین ببینید

• تجزیه کننده اولویت عملگر

منابع

1.  ویکی پدیای انگلیسی