mehdidanesh
یک شنبه 23 آبان 1389, 21:56 عصر
پشته می تواند به عنوان ابزاری برای بررسی پرانتزیک عبارت بکار گرفته شود. به این مفهوم که متناظر با هر پرانتز باز، یک پرانتز بسته در عبارت وجود داشته باشد. الگوریتمی بنویسید که عمل بررسی پرانتزی را انجام دهد
*****
A+B*((A^B)-(B^A))
الگوریتم:
- از ابتدای عبارت (سمت چپ) شروع کن
- یکی یکی کاراکترها را در پشته بریز (عمل PUSH را انجام بده)
- اگر پرانتز بسته به پشته اضافه شد، تا زمانیکه به یک پرانتز باز برسی، عمل POP را انجام بده. (یعنی کاراکترها را از پشته حذف کن)
- اگر به انتهای عبارت رسیدی، پشته را بررسی کن
- اگر پرانتزی (چه باز و چه بسته) داخل پشته بود، تعداد پرانتزهای باز و بسته یکی نیست و عبارت شامل خطا است. در غیر اینصورت، تعداد پرانتزهای باز و بسته مساوی است و عبارت صحیح است
*****
A+B*((A^B)-(B^A))
الگوریتم:
- از ابتدای عبارت (سمت چپ) شروع کن
- یکی یکی کاراکترها را در پشته بریز (عمل PUSH را انجام بده)
- اگر پرانتز بسته به پشته اضافه شد، تا زمانیکه به یک پرانتز باز برسی، عمل POP را انجام بده. (یعنی کاراکترها را از پشته حذف کن)
- اگر به انتهای عبارت رسیدی، پشته را بررسی کن
- اگر پرانتزی (چه باز و چه بسته) داخل پشته بود، تعداد پرانتزهای باز و بسته یکی نیست و عبارت شامل خطا است. در غیر اینصورت، تعداد پرانتزهای باز و بسته مساوی است و عبارت صحیح است