ماشین حساب (آشنایی با Syntax Diagram)

[Kambiz]

الگوریتم ماشین حسابی با تعریف زیر را بنویسید:
انجام چهار عمل اصلی با اولویت محاسباتی عملگرها طبق آنچه در زیر مشخص شده است:

+ - عملگر یگانی (Unary)
* /
+ - عملگر دودویی (Binary) عبارات داخل پرانتز از اولویت بالاتری برخوردارند.
اعداد می‌توانند صحیح یا اعشاری باشند.
پایان هر عبارت با علامت سوال (=) مشخص می‌شود.
خروج از ماشین حساب با ورود حرف ایکس (X) مشخص می‌شود.مثال:

2 * 3 + 4 * 5 =
26

2 * (3 + 4) * 5 =
70

2 * 3 + -4 * 5 =
-14

8.1 / -2.5 =
-3.24

X
شرایط الگوریتم:
برای گرفتن عبارت مورد محاسبه از کاربر٬ تنها یک تابع به نام GetChar وجود دارد که در هر زمان تنها یک کاراکتر از کاربر گرفته و آن را برمی‌گرداند.
به جز آخرین کاراکتر وارد شده توسط کاربر٬ الگوریتم نباید کاراکترهای قبلی وارد شده توسط کاربر را در متغیری ذخیره کند.
الگوریتم ارائه شده باید بر روی هر ماشین٬ سیستم عامل و زبان برنامه‌نویسی قابل پیاده‌سازی باشد.
----------------------
هدف از ارائه مسئله بالا٬ دستیابی به یک روش عمومی برای حل مسائل این چنینی است.

[Kambiz]

هیچکس حال نداره که یک راه حل ارائه بده؟ :(

[shaniaki]

با عرض ادب:


به جز آخرین کاراکتر وارد شده توسط کاربر٬ الگوریتم نباید کاراکترهای قبلی وارد شده توسط کاربر را در متغیری ذخیره کند.

در استفاده از از انواع دیگر متغیر ها چقدر آزادی وجود دارد؟
آیا ماشین فرضی ما مواردی مانند رویه ها یا فراخوانی یک رویه در داخل رویه ای دیگر(+ملاحظات مربوط به استفاده از پشته و ...) را پشتیبانی می کند؟

یه عشق برنامه نویسی خفن

[Kambiz]

سلام،

استفاده از متغیرهای از نوع ساده به هر میزان آزاده (آرایه یا رشته حروف نوع ساده نیستند) و از هر نوع فراخوانی هم می‌شه استفاده کرد.

از دو تا کلمه پشته و فراخوانی که بکار بردی پیداست که راه حل رو پیدا کردی. :wink:

[houshmand]

هیچکس حال نداره که یک راه حل ارائه بده؟ :(
خوب این برنامه این قدر ها هم ساده نیست
:!: که اگر قبلاٌ چنین برنامه ای ننوشته باشیم به توان به راحتی نوشت
مثلاُ چندین سال پیش یکی ازدوستان من داشت یک برنامه می نوشت که چک کند آیا تعداد پرانتز ها درست است یا نه ؟
من گفتم این که کاری ندارد: یک برنامه نوشتم که تعداد پرانتز ها را می شمرد آن هم اولین چیزی که وارد کرد یک چیزی شبیه این بود :cry:


)))5+4(((

/×××××××××××××××××××××××
خوب به جز مسایل محاسباتی اگر کاربر دو تا جمع وارد کرد چی
مثلاُ

5++6=
و خیلی چیز های دیگر ....

خوب قراره بهترین الگوریتم نوشته بشه :wink:

[Kambiz]

خوب این برنامه این قدر ها هم ساده نیست
با دونستن تکنیکی که باید برای حل اینجور مسائل بکار برده بشه زیاد هم سخت نیست. :wink:


خوب به جز مسایل محاسباتی اگر کاربر دو تا جمع وارد کرد چی
مثلاُ

5++6=
استثنا" این مثالی که زدی یک عبارت قابل قبوله چون طبق صورت مسئله هر دو علامت + و - به عنوان یک عملگر یگانی (تعیین علامت) تعریف شده‌اند. :)
ولی خوب همونجور که گفتی پیچیدگی این مسئله بیشتر در تشخیص درست یا نادرست بودن عبارت هست تا خود محاسبه.


خوب قراره بهترین الگوریتم نوشته بشه :wink:
حقیقتش نه! :oops:
اگر اینجا مسائلی اینچنینی مطرح می‌شه اصلا" هدف این نیست که بهترین الگوریتم براش نوشته بشه. آن چیزی که اهمیت داره چگونگی تحلیل مسئله و روش حل اونه.

[Kambiz]

در مورد الگوریتم ماشین حساب ما استفاده از یک بافر برای گرفتن عبارت بطور کامل و سپس تجزیه کردن اجزای (Parse) آن از لحاظ فنی غیر ممکن نیست و تنها بدلیل صورت مسئله قادر به انجام آن نیستیم. اما تصور کنید که اگر قرار بود مرورگرهای وب (Web Browsers) ابتدا تمام محتوای یک صفحه را بخواندند و سپس آن را تجزیه کرده و نمایش دهند چه مقدار زمان کاربر و سرویس دهنده وب به هدر می‌رفت و ترافیک بیهوده‌ای برروی خطوط ارتباطی حاصل می‌شد (در اکثر موارد ما با دیدن تنها چند خط از یک صفحه به صفحه دیگری می‌رویم).

در مورد ماشین حساب ورودی ما تنها یک عبارت ریاضی است که زیاد هم بزرگ نخواهد بود٬ اما متنی که توسط یک کامپایلر تجزیه تحلیل می‌شود می‌تواند به چندین میلیون خط هم برسد. در این حالت اگر کامپایلر نیاز داشت که تمام خطوط را در حافظه قرار دهد به چه میزان حافظه نیاز داشت تا تنها به این نکته پی ببرد که آیا خطایی در متن برنامه وجود دارد یا نه؟

در مواردی که ورودی ما از الگوی خاصی (Syntax) تبعیت می‌کند٬ به منظور یافتن الگوریتم مناسب برای تجزیه اجزا (Parse) و تفسیر معنای (Semantics) هر جزء از Syntax Diagram استفاده می‌شود.

همانند فلوچارت که می‌تواند برای نوشتن یک الگوریتم بکار ‌رود٬ Syntax Diagram هم روشی دیگر برای نوشتن یک الگوریتم است.

حال به یافتن الگوریتم ماشین حساب می‌پردازیم تا در این مثال به چگونگی استفاده از Syntax Diagram آشنا شوید.

برای ساده کردن عبارات از دوران ابتدایی آموخته‌ایم که:
هر عبارت داخل پرانتز خود می‌تواند به عنوان عبارتی مستقل محاسبه شده و در نهایت بصورت یک عدد در عبارت اولیه جایگزین شود.
علامتهای مثبت و منفی همواره پیش از یک عدد یا یک پرانتز قرار دارند (عملگرهای یگانی).
حاصل ضرب و تقسیم تمام اعدادی که با عملگرهای ضرب و تقسیم به هم مرتبط هستند بدون نیاز به اولویت‌بندی قابل محاسبه بوده و حاصل می‌تواند در عبارت اولیه جایگزین گردد (عملگرهای ضرب و تقسیم).
حاصل جمع و تفریق تمام اعدادی که مابین عملگرهای جمع و تفریق قرار دارند بدون نیاز به اولویت‌بندی قابل محاسبه هستند و حاصل می‌تواند در عبارت اولیه جایگزین گردد (عملگرهای جمع و تفریق دودویی).با این معلومات و با شروع از کلیات تا رسیدن به جزئیات (Top-Down Design) اقدام به طراحی الگوریتم می‌کنیم.


ماشین حساب:
http://delphiarea.com/external/calc/calculator.gif
ورودی می‌تواند حرف X باشد که در این صورت خارج می‌شویم یا یک عبارت و به دنبال آن علامت تساوی (=) که در این صورت دوباره از اول کار شروع می‌کنیم.


عبارت:
http://delphiarea.com/external/calc/expression.gif
یک عبارت تشکیل شده است از یک جمله یا حاصل جمع یا تفریق دو یا چند جمله.


جمله:
http://delphiarea.com/external/calc/term.gif
یک جمله تشکیل شده است از یک ضریب یا حاصل ضرب یا تقسیم دو یا چند ضریب.


ضریب:
http://delphiarea.com/external/calc/factor.gif
یک ضریب می‌تواند در ابتدا یکی از علامتهای مثبت یا منفی باشد و سپس، یا یک عدد یا یک عبارت داخل پرانتز (عبارت تعریفی است بازگشتی).


عدد:
http://delphiarea.com/external/calc/number.gif
یک عدد تشکیل شده است از یک نقطه (.) و سپس یک یا چند رقم، یا تنها یک یا چند رقم٬ یا یک یا چند رقم و سپس یک نقطه (.) و پس از آن یک یا چند رقم.


رقم:
http://delphiarea.com/external/calc/digit.gif
یک رقم یکی از حروف 0 تا 9 است.



خوب الگوریتم ما به همین سادگی نوشته شد. در هر مرحله٬ هرگاه ورودی با آنچه که در Syntax Diagram مربوطه انتظارش را داریم نخواند به معنی این است که عبارت مورد محاسبه نادرست وارد شده است.

در بالا برای ساده کردن Syntax Diagram ها فاصله‌ها را ندید گرفته‌ام ولی همانجور که پیداست به غیر از داخل یک عدد٬ در بقیه موارد لازم است که فاصله‌ها را ندید بگیریم. برای ایم منظور با استفاده از تابع GetChar که در صورت مسئله عنوان شده است٬ تابع دیگری می‌نویسیم که در آن بر حسب پارامتر تابع بتوانیم فاصله‌ها را رد کنیم. جدا از آن این تابع آخرین حرف خوانده شده را در داخل یک متغیر که توسط همه توابع قابل دسترسی است ذخیره می‌کند.


var
C: Char;

const
BlankChars = [' ', #9, #10, #13];

procedure FetchNextChar(SkipBlanks: Boolean);
begin
repeat
C := GetChar;
until not (SkipBlanks and (C in BlankChars));
end;
و بدنبال توابع مربوط به هر Syntax Diagram نوشته شده است. هر تابع در صورت برخورد با خطا مقدار False را برمی‌گرداند٬ والا مقدار برگشتی True است.


ماشین حساب:
http://delphiarea.com/external/calc/calculator.gif

procedure Calculator;
var
Value: Double;
begin
Writeln('Enter an expression or X to exit:');
FetchNextChar(True);
while C <> 'X' do
begin
if GetExpression(Value) and (C = '=') then
Writeln(Value)
else
begin
Writeln('Illegal expression!');
while C <> '=' do { ignores the rest of the illegal expression }
FetchNextChar(True);
end;
Writeln;
Writeln('Enter an expression or X to exit:');
FetchNextChar(True);
end;
end;

عبارت:
http://delphiarea.com/external/calc/expression.gif

function GetExpression(var Expr: Double): Boolean;
var
NextTerm: Double;
Op: Char;
begin
Result := False;
if GetTerm(Expr) then
begin
Result := True;
while Result and (C in ['+', '-']) do
begin
Op := C;
FetchNextChar(True);
Result := False;
if GetTerm(NextTerm) then
begin
case Op of
'+': Expr := Expr + NextTerm;
'-': Expr := Expr - NextTerm;
end;
Result := True;
end;
end;
end;
end;

جمله:
http://delphiarea.com/external/calc/term.gif

function GetTerm(var Term: Double): Boolean;
var
NextFactor: Double;
Op: Char;
begin
Result := False;
if GetFactor(Term) then
begin
Result := True;
while Result and (C in ['*', '/']) do
begin
Op := C;
FetchNextChar(True);
Result := False;
if GetFactor(NextFactor) then
begin
if Op = '*' then
begin
Term := Term * NextFactor;
Result := True;
end
else if NextFactor <> 0 then
begin
Term := Term / NextFactor;
Result := True;
end;
end;
end;
end;
end;

ضریب:
http://delphiarea.com/external/calc/factor.gif

function GetFactor(var Factor: Double): Boolean;
var
Negate: Boolean;
begin
Result := False;
Negate := False;
if C in ['+', '-'] then
begin
if C = '-' then
Negate := True;
FetchNextChar(True);
end;
if C = '(' then
begin
FetchNextChar(True);
if GetExpression(Factor) and (C = ')') then
begin
FetchNextChar(True);
Result := True;
end;
end
else if GetNumber(Factor) then
Result := True;
if Negate then
Factor := -Factor;
end;

عدد:
http://delphiarea.com/external/calc/number.gif

function GetNumber(var Number: Double): Boolean;
var
Digit: Integer;
Fraction: Double;
PointPos, P: Integer;
begin
Result := False;
Number := 0;
while GetDigit(Digit) do
begin
Number := Number * 10 + Digit;
FetchNextChar(False);
Result := True;
end;
if C = '.' then
begin
FetchNextChar(False);
PointPos := 0;
while GetDigit(Digit) do
begin
Fraction := Digit;
Inc(PointPos);
for P := 1 to PointPos do
Fraction := Fraction / 10;
Number := Number + Fraction;
FetchNextChar(False);
Result := True;
end;
end;
if C in BlankChars then
FetchNextChar(True);
end;

رقم:
http://delphiarea.com/external/calc/digit.gif

function GetDigit(var Digit: Integer): Boolean;
begin
Result := False;
if C in ['0'..'9'] then
begin
Digit := Ord(C) - Ord('0');
Result := True;
end;
end;

برای تمرین سعی کنید با استفاده از Syntax Diagram عملگری برای به توان رساندن و چند تابع ریاضی (مثل Sin و Cos و ...) به ماشین حساب اضافه کنید.

[Farhadi]

بحث جالبیه
حیف که دیر رسیدم.

من دو سال پیش یه برنامه نوشته بودم که معادله تابع رو میگیره و نمودار تابع رو رسم میکنه.
روش محاسباتی این برنامه بسیار شبیه به الگوریتم ماشین حساب است با این تفاوت که x را به عنوان متغییر در نظر میگیره و از توابع دیگه هم میشه توی معادله استفاده کرد.

توابعی که میشه داخل معادله استفاده کرد عبارتند از :
sin - cos - tan - cot - abs - sqrt - ln - arctan - e - int - pi

عملگرهای قابل استفاده عبارتند از : + ، - ، * ، / ، ^

از پرانتز هم میشه در معادله استفاده کرد.

ترتیب عملگرها مشابه ترتیب اونها در برنامه نویسی است.

فایلهای مربوط به برنامه رو attach کردم.
ولی پیشنهاد میکنم سورسش رو دانلود نکنید.
چون من خیلی قاتی پاتی برنامه نویسی میکنم فکر نمیکنم بفهمین چیکار کردم. :lol:

روش استفاده از برنامه به این صورته که معادله مورد نظر رو در قسمت بالای برنامه مینویسید و enter میزنید و نمودار تابع رسم میشود. به همین سادگی ...

برای مثال یکی از معادله های زیر رو امتحان کنید :<span dir=ltr>
sin(x)
x^2+3*x
sin(x)*cos(x)
abs(sin(x))
sin(x^2)
</span>
در ضمن می تونید روی صفحه حرکت کنید و زوم کنید و نشانگر موس هم مختصات شما را نشان میدهد.

با تشکر،
علی فرهادی

[shamsi_m]

سلام.
برنامه کاملی رو می خوام که نمودار sin x +ln x رو رسم کنه. می شه کمکم کنین؟؟:لبخندساده:
ممنون. shahparsan@gmail.com