طراحی وب سایت

کامپیوتر عبارت را چگونه حساب می کند؟ این فرم عبارت که در تمام دوران به ما یاد دادند به infix معروف است و ساده ترین مدل از نمایش یک عبارت ریاضی است. اگر کامپیوتر قرار باشد عبارت بالا را همان گونه که ما در ذهن خود محاسبه می کنیم، محاسبه کند، هم هزینه زیادی دارد و هم این که زمان زیادی می برد. اما واقعا کامپیوتر این عبارت را در کمترین زمان با بیشترین دقت حل می کند؟
برای کامپیوتر دو مدل از نمایش عبارات ریاضی تعریف شده است: یکی (postfix) و دیگری پیشوندی (prefix). کامپیوتر عبارت میانوندی (infix) را گرفته و مدل پسوندی یا پیشوندی آن را به دست می آورد و نتیجه آن را محاسبه می کند.
اما مدل پسوندی یا پیشوندی چه هستند؟
فرض کنیم عبارت میانوندی ما a*b+c/d باشد. مدل معادل پسوندی آن به صورت خواهد بود و مدل پیشوندی آن به صورت این مدل از نمایش از تجزیه یک عبارت میانوندی به دست می آید که بر اساس تقدم عملگر ها به دست می آید. مثلا تقدم عملگر * از + و / جلوتر است پس زودتر محاسبه می شود. و بین / و +، / تقدمی بیشتر دارد پس زودتر در عبارت می آید.
حال چگونه یک عبارت میانوندی را به یک عبارت پسوندی تبدیل کنیم؟
برای این کار از ساختار داده ای به نام پشته (stack) استفاده می کنیم. در مورد پشته پیش از این صحبت کردیم، اما برای یاد آوری:
پشته یک آرایه است که از ساختار lifo (last input first output) پیروی می کند، یعنی اولین عنصر ورودی آخرین عنصر خروجی است. بهترین مثالی که می توان در مورد پشته زد این است که فرض کنید که چند کتاب دارید و آنها را می خواهید در یک کارتن قرار دهید، کتاب ها را می چینید تا کارتن پر شود. برای دسترسی به اولین کتابی که درون کارتن قرار داده اید نیاز است که تمامی کتاب ها را در آوردید را در بیاورید و سپس به آن برسید، پس اول همه را بیرون می آوریم، سپس اولی را برمی داریم. اما اگر خواستیم به آخرین کتاب دسترسی پیدا کنیم، باید همان کتاب آخر را برداریم و برای دسترسی به آن نیازی به بیرون کشیدن کتاب دیگری نیست.
بسیار خب، همان طور که می دانید در زبان های برنامه نویسی، علایم و عملوند ها داری تقدم نسبت به یکدیگر هستند، مثلا عملگر () نسبت به * دارای تقدم است و همین طور * نسبت به + و ... برای مشاهده تقدم عملگر ها در زبان های برنامه نویسی، نشانی زیر را ببینید:
http://en.wikipedia.org/wiki/order_of_operations
پس اگر داشته باشیم a+b*c اول b در c ضرب می شود و سپس حاصل با a جمع می شود، حال اگر داشته باشیم که ابتدا b با c جمع می شود و سپس حاصل در a ضرب می شود همان طور که می بینید، همین تقدم عملگر ها را ما در ریاضی و هنگام محاسبه ذهنی و دستی عبارت آن را لحاظ می کنیم. پس چیز پیچیده وسختی نیست.
خب حال ما با استفاده از پشته و همین تقدم عملگر ها یک عبارت میانوندی را به عبارت پسوندی تبدیل می کنیم.
برای این کار نیاز به دو پشته داریم یکی که به صورت موقت مورد استفاده قرار می گیرد و یکی هم که نتیجه در آن قرار می گیرد.
کاری که ما می کنیم این است کاراکتر به کاراکتر عبارت را می خوانیم و اگر عدد بود، در پشته نتیجه (آن را result می نامیم) قرار می دهیم و اگر عملوند بود در پشته موقت (آن را temp می نامیم) ذخیره می کنیم.
پس از خواندن اولین کاراکتر مقدار result برابر ? است و مقدار temp مقداری ندارد. پس از خواندن کاراکتر بعدی، مقدار result همان ? می ماند و مقدار temp برابر + می شود، در مرحله بعد مقدار result تغییری نمی کند و کاراکتر ) در temp قرار می گیرد، در مرحله بعد نیز مقدار result برابر است ولی مقدار temp بدون تغییر می ماند. این کار به همین صورت انجام می شود.
اگر بخواهیم برای آن قاعده کلی تعریف کنیم، به این صورت است که ابتدا تمامی عملگر ها در result قرار می گیرند و تغییری نمی کند، اما مقدار temp مدام تغییر می کند، یعنی پر و خالی می شود و مقدار آن به result افزوده می شود، شرط اضافه شدن آیتمی از temp به result برخورد به علامت ( یا تمام شدن کاراکتر های عبارت ریاضی است، هر وقت به یکی از این دو عملوند رسید، مقدار temp را در result قرار می دهد (آیتم های درون temp از آن خارج می شوند و داخل result قرار می گیرند این کار به وسیله دو تابع در پشته به نام های push و pop انجام می شود، push به معنای وارد کردن و pop به معنای خارج کردن است).
نکته ای که باید به آن دقت کنید این است زمانی یک عملوند به temp اضافه شود که اولویت آن از اولویت آخرین عضو temp کمتر باشد، اگر بیشتر بود به result منتقل می شود.برای مثال بالا پس از پایان مراحل وقتی به کاراکتر ( رسیدیم، مقدار result برابر abc است و مقدار temp برابر +/)+ است و بعد از این مرحله آنقدر آیتم از temp خارج می شود که تا به اولین) برسیم در نتیجه پس از این مرحله مقدار result برابر /abc2+ می شود و چون کاراکتر ها به پایان رسیده، همه آیتم های موجود در temp به result اضافه می شود، که عبارت حاصل برابر با /abc2+ خواهد شد.
امیر بهاالدین سبط الشیخ

منبع : جام جم آنلاین  تاریخ : 28   شهریور   1389  شاخه : برنامه نویسی