منظور از یک پشته، یک لیست ات که تنها می‌توانیم عنصری را به انتهای آن اضافه کنیم (که به این عمل $push$ می‌گویند)، و یا عنصری را از انتهای آن برداریم (به این عمل نیز $Pop$ گفته می‌شود). به عبارت دیگر، پشته، ساختاری است که هرگاه بخواهیم از داخل آن عنصری را برداریم، آخرین عنصری که به آن وارد شده است، برداشته می‌شود.

یک ماشین $PDA$، به این صورت تعریف می‌شود: ماشین دارای یک پشته است و بر اساس یک برنامه، از ورودی رشته‌ای را دریافت می‌کند و عملیاتی را انجام می‌دهد. رشته‌ی ورودی ماشین، دنباله‌ای از یک مجموعه‌ی متناهی است که به آن الفبا می‌گوییم. در این مسئله، فرض کنید که الفبایی که ماشین با آن کار می‌کند، مجموعه‌ی $A=\{0,1,+,*,(,), \$ \}$ است. البته فرض کنید که رشته‌ی ورودی هیچ‌گاه شامل حرف $ نیست. برنامه‌ای که ماشین بر اساس آن عمل می‌کند، از تعدادی «دستور» تشکیل شده است. هر دستوری دارای یک شماره است. (شماره‌ی دو دستور نمی‌تواند یکسان باشد.) اجرای برنامه از دستور شماره‌ی ۱ شروع می‌شود و هر دستور مشخص می‌کند که چه دستوری پس از خودش اجرا شود. اگر دستوری که قرار است اجرا شود در برنامه‌ وجود نداشته باشد، اجرای برنامه متوقف می‌شود.

ماشین سه دستور زیر را می‌شناسد:

• دستور $Push$: شکل این دستور به صورت زیر است. ($l$ شماره‌ی دستور است.)

$$l:Push[x,n]$$

این دستور، $x$ را روی پشته $Push$ می‌کند ( $x$ می‌تواند هر یک از اعضای $A$ به‌جز حرف $ \$ $ باشد.) و پس از آن دستور شماره‌ی $n$ را اجرا می‌کند.

• دستور $Pop$: شکل این دستوربه صورت زیر است:

$$l: Pop[x_1,n_1][x_2,n_2]…$$

این دستور، یک عنصر را از روی پشته $Pop$ می‌کند. اگر این عنصر $x_1$ بود، پس از این دستور، دستور شماره‌ی $n_1$ اجرا می‌شود، اگر $x_2$ بود، دستور شماره‌ی $n_2$ اجرا می‌شود و … . در صورتی که عنصری که از روی پشته $Pop$ شده است، مساوی با هیچ یک از $x_i$ ها نبود، اجرای برنامه خاتمه می‌یابد.

• دستور $Read$: شکل این دستور به صورت زیر است:

$$l: Read [x_1,n_1][x_2,n_2]…$$

این دستور، عنصر بعدی رشته‌ی ورودی را می‌خواند و بسته به این که مقدار این عنصر برابر با کدام یک از $x_i$ ها باشد، دستور با شماره‌ی $n_i$ متناظر را پس از این دستور اجرا می‌کند. اگر عنصر خوانده شده، مساوی با هیچ یک از $x_i$ ها نبود، اجرای برنامه خاتمه می‌یابد.

برای مشخص کردن انتهای رشته‌ی ورودی، قرارداد می‌کنیم که هر گاه به پایان رشته‌ی ورودی رسیدیم و دوباره دستور $Read$ اجرا شد، حرف $ از ورودی خوانده می‌شود.

همچنین اگر پشته خالی باشد و دستور $Pop$ اجرا شود (برا مثال اگر در ابتدای کار، قبل از این که چیزی را به پشته $Push$ کرده باشیم، عمل $Pop$ را انجام دهیم)، حرف $ از روی پشته خوانده می‌شود.

حرف $ \$ $ فقط به این منظور در الفبا قرار داده شده است و همان‌طور که گفته شد، این حرف در رشته‌ی ورودی وجود ندارد و همچنین حق نداریم این حرف را به پشته $Push$ کنیم.

به مثال زیر توجه کنید. در این مثال، برنامه یک رشته که تنها از حروف $($ و $)$ تشکیل شده است را به عنوان ورودی می‌گیرد و چک می‌کند که آیا این پرانتز‌ها درست قرار گرفته‌اند یا خیر. در صورتی که پرانتز‌ها درست قرار گرفته بودند، پس از پایان اجرای برنامه، تنها حرف ۱ و در غیر این صورت تنها حرف ۰ روی پشته وجود دارد.

الف) فرض کنید ورودی رشته‌ای از حروف 0، ۱، + و * است که یک عبارت محاسباتی ساده را مشخص می‌کند؛ یعنی رشته با یکی از حروف 0 یا ۱ شروع می‌شود، پس از آن با یکی از عمل‌گرهای + یا *، سپس یکی از حروف 0 یا ۱ و به همین صورت یک‌در‌میان ادامه می‌یابد و آخرین حرف رشته نیز یکی از حرف 0 یا ۱ است. مقدار این رشته، مانند عبارت‌های محاسباتی جبری حساب می‌شود، تنها با این تفاوت که مقدار $1+1$ برابر با ۱ است. (یعنی در حقیقت عمل + مانند عمل «یا» ی منطقی است.) بنابراین مقدار چنین عبارتی 0 یا ۱ است. همچنین عمل‌گر * نسبت به عمل‌گر + اولویت دارد؛ یعنی برای مثال مقدار عبارت $1+0*0$ برابر با ۱ است.

برنامه‌ای برای ماشین $PDA$ بنویسید که یک رشته‌ی ورودی به صورت فوق را به طور کامل خوانده، به گونه‌ای عمل کند که زمانی که متوقف می‌شود، تنها یک عدد 0 یا ۱ که برابر مقدار عبارت ورودی است، روی پشته باشد. برنامه‌ی شما نباید شامل بیش از ۱۵ دستور باشد.

ب) در این قسمت فرض کنید که رشته‌ی ورودی ماشین، عبارتی محاسباتی است که می‌تواند شامل پرانتز هم باشد. اهمیت پرانتز در این است که ترتیب محاسبه‌ی عمل‌گرها را تغییر می‌دهد. برای مثال مقدار عبارت $(1+0)*0$ برابر با 0 است؛ در حال که اگر پرانتزها وجود نداشتند، مقدار این عبارت برابر با ۱ بود. برنامه‌ای بنویسید که چنین عبارتی را به عنوان رشته‌ی ورودی بگیرد و به گونه‌ای عمل کند که زمانی که متوقف می‌شود، مقدار عبارت روی پشته قرار گرفته باشد. برنامه‌ی شما نباید شامل بیش از ۲۵ دستور باشد.

• سوال بعد
• سوال قبل