این سوال تو کتاب مدرسان بود, من متوجه نمیشم چطوری حل شده! کسی میتونه توضیح بده؟؟؟
[img]
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
[/img]
سلام
الگوریتم این کار اینه که هر وفت به (پرانتز، کروشه یا آکولاد) باز می‌رسیم، اون رو توی پشته می‌ریزیم و هر وفت به (پرانتز، پشته یا آکولاد) بسته می‌رسیم، یک عمل POP انجام می‌دیم. در آخر کار اگر پشته خالی بود، می‌فهمیم جواب درسته.
در این سوال عبارت رو پیمایش میکنیم، اول } رو می‌ریزیم توی پشته بعد ) و ]، حالا به [ (بسته) می‌رسیم، پس عمل پاپ از پشته رو انجام می‌دیم. بعد همینطور می‌ریم جلو تا آخر. شما باید این مسیر رو تا آخر پیمایش کنی و در آخر ببینی بیشترین تعدادی که در طول عملیات در پشته داشتی چقدر بوده
امیدوارم منظورمو خوب منتقل کرده باشم.
(۲۲ آبان ۱۳۹۳ ۱۲:۰۲ ق.ظ)soheil08 نوشته شده توسط: سلام
الگوریتم این کار اینه که هر وفت به (پرانتز، کروشه یا آکولاد) باز می‌رسیم، اون رو توی پشته می‌ریزیم و هر وفت به (پرانتز، پشته یا آکولاد) بسته می‌رسیم، یک عمل POP انجام می‌دیم. در آخر کار اگر پشته خالی بود، می‌فهمیم جواب درسته.
در این سوال عبارت رو پیمایش میکنیم، اول } رو می‌ریزیم توی پشته بعد ) و ]، حالا به [ (بسته) می‌رسیم، پس عمل پاپ از پشته رو انجام می‌دیم. بعد همینطور می‌ریم جلو تا آخر. شما باید این مسیر رو تا آخر پیمایش کنی و در آخر ببینی بیشترین تعدادی که در طول عملیات در پشته داشتی چقدر بوده
امیدوارم منظورمو خوب منتقل کرده باشم.
منظورتونو متوجه شدم ولی اینکه چرا گزینه ۱ میشه رو نمیفهمم, آخه ۴ تا گنجایش داشته باشه مگه میشه کاری کرد؟؟!! مشکل من در تعداد حداقل گنجایش هست, میشه این رو توضیح بدید؟!
پیمایش از چپ شروع میشه وقتی به یه پرانتز یا براکت باز میرسه اونو میذاره پشته و هر وقت به پرانتز بسته میرسه اونو با بالای پشته تطبیق میده اگر برابر باشن از بالای پشته پرانتز یا براکت رو حذف میکنه یعنی پرانتز و براکت بسته اصلا وارد پشته نمیشه همینطور که تو عکس میبینید بیشترین تعداد خانه پشته ۴تا اشغال میشه
![[تصویر: 315665_IMG_20141113_090359.jpg]](https://img.manesht.ir/315665_IMG_20141113_090359.jpg)
سلام.ببین هر چی پرانتز باز و اکولاد باز و کروشه باز رو Push میکنیم و به بسته هرکدوم رسیدیم با بالای پشته مقایسه میکنیم اگه تطابق داشت Pop میکنیم و اگه تطابق نداشت اعلام خطا و وقتی کل ورودی پیمایش شد اگه پشته خالی شد تطابق وجود داره
خب حالا حل سوال::[بالای پشته رو سمت چپ فرض کن]
محتویات پشته[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex][tex]empty[/tex]
عنصر ورودی[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex]}
طول پشته[tex]0\leftarrow[/tex]
عملیات[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex][tex][tex]Push[/tex][/tex]
[tex][tex][tex]--------------------------[/tex][/tex][/tex]
محتویات پشته[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex]}
عنصر ورودی[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex])
طول پشته[tex]1\leftarrow[/tex]
عملیات[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex][tex][tex]Push[/tex][/tex]
[tex][tex][tex]--------------------------[/tex][/tex][/tex]
محتویات پشته[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex]},)
عنصر ورودی[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex]]
طول پشته[tex]2\leftarrow[/tex]
عملیات[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex][tex][tex]Push[/tex][/tex]
[tex][tex][tex]--------------------------[/tex][/tex][/tex]
محتویات پشته[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex]},),]
عنصر ورودی[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex][
طول پشته[tex]3\leftarrow[/tex]
عملیات[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex][tex][tex]Pop[/tex][/tex]
[tex][tex][tex]--------------------------[/tex][/tex][/tex]
محتویات پشته[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex]},)
عنصر ورودی[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex]]
طول پشته[tex]2\leftarrow[/tex]
عملیات[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex][tex][tex]Push[/tex][/tex]
[tex][tex][tex]--------------------------[/tex][/tex][/tex]
محتویات پشته[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex]},),]
عنصر ورودی[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex])
طول پشته[tex]3\leftarrow[/tex]
عملیات[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex][tex][tex]Push[/tex][/tex]
[tex][tex][tex]--------------------------[/tex][/tex][/tex]
محتویات پشته[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex]},),],)
عنصر ورودی[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex](
طول پشته[tex]4\leftarrow[/tex]
عملیات[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex][tex][tex]Pop[/tex][/tex]
[tex][tex][tex]--------------------------[/tex][/tex][/tex]
محتویات پشته[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex]},),]
عنصر ورودی[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex][
طول پشته[tex]3\leftarrow[/tex]
عملیات[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex][tex][tex]Pop[/tex][/tex]
[tex][tex][tex]--------------------------[/tex][/tex][/tex]
محتویات پشته[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex]},)
عنصر ورودی[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex](
طول پشته[tex]2\leftarrow[/tex]
عملیات[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex][tex][tex]Pop[/tex][/tex]
[tex][tex][tex]--------------------------[/tex][/tex][/tex]
محتویات پشته[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex]}
عنصر ورودی[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex]{
طول پشته[tex]1\leftarrow[/tex]
عملیات[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex][tex][tex]Pop[/tex][/tex]
[tex][tex][tex]--------------------------[/tex][/tex][/tex]
محتویات پشته[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex]
عنصر ورودی[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex])
طول پشته[tex]0\leftarrow[/tex]
عملیات[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex][tex][tex]Push[/tex][/tex]
[tex][tex][tex]--------------------------[/tex][/tex][/tex]
محتویات پشته[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex])
عنصر ورودی[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex])
طول پشته[tex]1\leftarrow[/tex]
عملیات[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex][tex][tex]Push[/tex][/tex]
[tex][tex][tex]--------------------------[/tex][/tex][/tex]
محتویات پشته[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex]),)
عنصر ورودی[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex]]
طول پشته[tex]2\leftarrow[/tex]
عملیات[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex][tex][tex]Push[/tex][/tex]
[tex][tex][tex]--------------------------[/tex][/tex][/tex]
محتویات پشته[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex]),),]
عنصر ورودی[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex][
طول پشته[tex]3\leftarrow[/tex]
عملیات[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex][tex][tex]Pop[/tex][/tex]
[tex][tex][tex]--------------------------[/tex][/tex][/tex]
محتویات پشته[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex]),)
عنصر ورودی[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex](
طول پشته[tex]2\leftarrow[/tex]
عملیات[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex][tex][tex]Pop[/tex][/tex]
[tex][tex][tex]--------------------------[/tex][/tex][/tex]
محتویات پشته[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex])
عنصر ورودی[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex](
طول پشته[tex]1\leftarrow[/tex]
عملیات[tex][tex][tex][tex][tex][tex][tex]\leftarrow[/tex][/tex][/tex][/tex][/tex][/tex][/tex][tex][tex]Pop[/tex][/tex]
[tex][tex][tex]--------------------------[/tex][/tex][/tex]
خب رشته تموم شد و پشته هم خالیه.ببین ما بیشترین عنصری که توی پشته داشتیم ۴ عنصر بود و هیچ وقت در مراحل پیمایش طول پشته از ۴ بیشتر نشد.پس گنجایش پشته باید حداقل ۴ باشه
من مشکل و اشتباهم این بود که علاوه بر پرانتز و براکت و آکولاد , سایر عناصر رو هم وارد پشته میکردم!
ممنون از توضیحاتتون دوستان
