دسته : ad hoc
توضیح سوال: ابتدای ورودی لیستی از ماتریس ها که شامل نام و اندازه ی ماتریس ها می باشد داده می شود. اسم ماتریس حروف بزرگ می باشد که از ۲۶ تا ماتریس بیشتر نمی تواند باشد. بعد از آن لیستی شامل پرانتز ها و اسامی ماتریس ها داده می شود که شما می بایست تعداد عملیاتی که برای محاسبه ی این عبارت انجام می شود را به عنوان خروجی چاپ کنید این نکته هم نباید فراموش شود که ممکن است عبارت قانون ضرب ها را رعایت نکند که در این صورت باید error چاپ شود.
در سوال بر اساس Extended Backus–Naur Form قوانینی که بر اجرای آنها تاکید شده است داده شده که بدین شرح است.
SecondPart = Line { Line } <EOF>
Line = Expression <CR>
Expression = Matrix | "(" Expression Expression ")"
Matrix = "A" | "B" | "C" | ... | "X" | "Y" | "Z"
براساس Extended Backus–Naur Form :
= defining-symbol تعریف
{ ... } repetition تکرار
| alternation ترتیب
نکات خوبی از این قوانین میشه استخراج کرد برای مثال از قسمت Expression که به صورت بازگشتی تعریف شده میشه فهمید که داخلی ترین پرانتز فقط شامل دو ماتریس است نه کمتر و نه بیشتر.
.
توضیح راه حل: اگر شما بتوانید از پس نمونه ورودی های این سوال بر بیایید به راحتی Accepte این سوال رو خواهید گرفت. برای اطمینان summation یا به عبارت دیگر خروجی را long long بگیرید.
کاری که می بایست انجام دهید این است که شروع به وارد کردن عبارت در داخل stack کنید. زمانی که به '(' رسیدید باید به پردازش دو عنصر آخر که حتما دو ماتریس است بپردازید و بعد سومین عنصر آخر stack که ')' به همراه دو ماتریس از stack خارج کنید و ماتریس حاصلشان را داخل stack قرار دهید.
با استفاده از یک vector از نوع pair می توانید به ماتریس های لیست اول ورودی و ماتریس های جدیدی که در عبارت بوجود می آید دسترسی پیدا کنید.
پیشنهاد من این است که نوع stack از نوع int باشد که در این صورت ماتریس ها را با ایندکس vector و ')' را منفی یک قرار دهید.
