عبارات ریاضی در کامپیوتر

برای کامپیوتر دو مدل از نمایش عبارات ریاضی تعریف شده است: یکی (Postfix) و دیگری پیشوندی (Prefix). کامپیوتر عبارت میانوندی (Infix) را گرفته و مدل پسوندی یا پیشوندی آن را به‌دست می‌آورد و نتیجه آن را محاسبه می‌کند.

فرض کنیم عبارت میانوندی ما A*B+C/D باشد. مدل معادل پسوندی آن به‌صورت خواهد بود و مدل پیشوندی آن به‌صورت این مدل از نمایش از تجزیه یک عبارت میانوندی به‌دست می‌آید که بر اساس تقدم عملگر‌ها به‌دست می‌آید. مثلا تقدم عملگر * از + و / جلوتر است پس زودتر محاسبه می‌شود. و بین / و +، / تقدمی بیشتر دارد پس زودتر در عبارت می‌آید.

برای این کار از ساختار داده‌ای به نام پشته (Stack) استفاده می‌کنیم. در مورد پشته پیش از این صحبت کردیم، اما برای یاد‌آوری:

پشته یک آرایه است که از ساختار LIFO (Last Input First Output) پیروی می‌کند، یعنی اولین عنصر ورودی آخرین عنصر خروجی است. بهترین مثالی که می‌توان در مورد پشته زد این است که فرض کنید که چند کتاب دارید و آنها را می‌خواهید در یک کارتن قرار دهید، کتاب‌ها را می‌چینید تا کارتن پر شود. برای دسترسی به اولین کتابی که درون کارتن قرار داده‌اید نیاز است که تمامی کتاب‌ها را در آوردید را در بیاورید و سپس به آن برسید، پس اول همه را بیرون می‌آوریم، سپس اولی را برمی‌داریم. اما اگر خواستیم به آخرین کتاب دسترسی پیدا کنیم، باید همان کتاب آخر را برداریم و برای دسترسی به آن نیازی به بیرون کشیدن کتاب دیگری نیست.

بسیار خب، همان‌طور که می‌دانید در زبان‌های برنامه‌نویسی، علایم و عملوند‌ها داری تقدم نسبت به یکدیگر هستند، مثلا عملگر () نسبت به * دارای تقدم است و همین‌طور * نسبت به + و ... برای مشاهده تقدم عملگر‌ها در زبان‌های برنامه‌نویسی، نشانی زیر را ببینید:

پس اگر داشته باشیم a+b*c اول b در c ضرب می‌شود و سپس حاصل با a جمع می‌شود، حال اگر داشته باشیم که ابتدا b با c‌ جمع می‌شود و سپس حاصل در a ضرب می‌شود همان‌طور که می‌بینید، همین تقدم عملگر‌ها را ما در ریاضی و هنگام محاسبه ذهنی و دستی عبارت آن را لحاظ می‌کنیم. پس چیز پیچیده وسختی نیست.

خب حال ما با استفاده از پشته و همین تقدم عملگر‌ها یک عبارت میانوندی را به عبارت پسوندی تبدیل می‌کنیم.

برای این کار نیاز به دو پشته داریم یکی که به‌صورت موقت مورد استفاده قرار می‌گیرد و یکی هم که نتیجه در آن قرار می‌گیرد.

کاری که ما می‌کنیم این است کاراکتر به کاراکتر عبارت را می‌خوانیم و اگر عدد بود، در پشته نتیجه (آن را result می‌نامیم) قرار می‌دهیم و اگر عملوند بود در پشته موقت (آن را temp می‌نامیم) ذخیره می‌کنیم.

پس از خواندن اولین کاراکتر مقدار result برابر 2 است و مقدار temp مقداری ندارد. پس از خواندن کاراکتر بعدی، مقدار result همان 2 می‌ماند و مقدار 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+ خواهد شد.