PDA

View Full Version : پرانتز در برنامه ماشین حساب



farhadamin
پنج شنبه 29 فروردین 1387, 11:29 صبح
سلام می خواستم یک برنامه ماشین حساب بنویسم.... اما با پرانتز مشکل داره... می خواستم ببینم چه جوری می شه کاری کرد که برنامه پرانتز را بشناسد.... و درست محاسبه کند..... ممنون می شم راهنمایی کنید...
و مثلا بشه یک همچن چیزی را استفاده کرد.....

void mandatory2_test()
{
// requires:
// #include <iostream>
// #include <vector>
// #include <stdexcept>
//
// and inclusion of all relevent operator header files.
using std::cout; using std::endl;
std::vector<Expr *> expressions;
Num num5( 5 );
Num num1( 1 );
Num num2( 2 );
Num num0( 0 );
Plus ex_plus2_5( &num2, &num5 );
Minus ex_minus( &ex_plus2_5, &num1 );
Mult ex_mul( &ex_plus2_5, &ex_minus );
expressions.push_back( &ex_mul );
Div ex_div7_5( &ex_plus2_5, &num5 );
expressions.push_back( &ex_div7_5 );
Pow ex_pow( &num5, &num2 );
expressions.push_back( &ex_pow );
Pow ex_pow2( &num1, &ex_mul );
expressions.push_back( &ex_pow2 );
Exp ex_exp( &num2 );
expressions.push_back( &ex_exp );
Sqrt ex_sqrt( &num2 );
expressions.push_back( &ex_sqrt );
Mult ex_( &ex_pow, &ex_sqrt );
expressions.push_back( &ex_ );
for( int i = 0; i < expressions.size(); ++i )
cout << expressions[i]->toString() << " = " << expressions[i]->eval() << endl;
Div ex_dbz( &num2, &num0 );
try{
cout << ex_dbz.toString(); cout.flush();
ex_dbz.eval();
}
catch (std::domain_error ex) {
cout << "Exception: " << ex.what() << endl;
}
}

MRHagh
پنج شنبه 29 فروردین 1387, 21:50 عصر
ساز و کار ماشین حساب معمولا به این صورت است که ابتدا عبارت وارد شده را از حالت infixe (فرمی که ما معمولا برای نوشتن عبارات ریاضی روی کاغذ استفاده میکنیم) به حالت postfixe یا prefixe (پسوندی یا پیشوندی) تبدیل میکند . خاصیت این کار این است که :
1. اولویت عملگرها بی دردسر رعایت میشود
2. هرگونه پرانتز از رشته محاسبات حذف میشود
اوصولا برای چنین تبدیلی (infixed به postfixe) از ساختار پشته استفاده میشود که قوانین push و pop در آن از قرار زیر است :
1. هرگاه در رشته به عملوند رسیدیم یا چاپ میکنیم یا در پشته دیگر قرار میدهیم(بسته به کاری که میخواهیم انجام دهیم)
2. هرگاه به عملگر رسیدیم به پشته push میکنیم , به این ترتیب که اگر عملگری که در موقعیت top پشته بود دارای اولویت بالاتری نسبت به عملگری که قصد وارد کردن آنرا به پشته داریم داشت , ابتدا آنرا pop کرده سپس عملگر را با رعایت دوباره این نکته push میکنیم
3.اگر به پرانتز چپ رسیدیم بدون هیچ شرطی آنرا push میکنیم و باقی عملگرها را با حفظ شرط گفته شده push میکنیم , وقتی به پرانتز راست رسیدیم , پشته را تا جایی که به پرانتز چپ برسیم خالی میکنیم .
4. هرگاه به انتهای رشته رسیدیم , پشته را خالی میکنیم.
اما برای ماشن حساب لازم است شما از دو پشته استفاده کنید , به صورتی که در یکی عملگر و در دیگری عملوند بریزید , هرگاه عملگری از پشته عملگرها pop شد باید دو عملوند از پشته عملوندها pop و پس از تاثیر عملگر pop شده , حاصل دوباره در پشته عملوندها push شود . تاجایی که پشته عملگرها خالی شود , در این لحظه حاصل عبارت وارد شده , تنها عدد باقیمانده در پشته عملوندهاست .

MRHagh
یک شنبه 01 اردیبهشت 1387, 18:10 عصر
همانطوریکه قبلا اشاره شد , شما برای طراحی ماشین حساب در اولین مرحله با مسئله اعمال اولویت عملگرها مواجه هستید , بنابراین بهترین راه حل طراحی یک پشته با ساختار مناسب است (البته با روشهای دیگر , نظیر استفاده مناسب از دو حلقه تودرتو که در اصل هم شبیه سازی پشته است هم میتوان این منظور را پیاده سازی کرد) .
اصولا در نمایش عبارات ریاضی از سه فرم قابل قبول استفاده میکنیم که در این بین , فرم Infdix به عنوان شکل استاندارد شناخته شده است , چرا که در این روش عملگرهای دودوئی را در بین عملوندها یا به عبارتی سر جای اصلی خودشان قرار میدهیم . مثال ریز شکل نمایش یک عبارت ریاضی در فرم Infix است :

2+325+481-536*(65-89)-45
مشاهده میکنید که این روش همان روش همیشگی ما برای نمایش عبرات ریاضی است . با وجود اینکه نشانه گذاری های Infix معمولی ترین شکل نمایش عبارات است , ولی کامپایلر ها قادر به استفاده از آن برای ارزشیابی عبارات نیستند . وجود پرانتزها و همینطور عدم آگاهی از عملگر بعدی که وارد محاسبه میشود و آیا اولویتش از عملگر کنونی بالاتر است یا خیر , اساسی ترین معایب این شکل نمادگذاری عبارات , برای استفاده از آن در تحلیل به کمک کامپیوتر است .
برای رهایی از معایب یاد شده , فرم دیگری از نمایش عبارات ساخته شد که در آن دیگر خبری از پرانتز نیست و عملگرها دیگر در بین عملوندهایشان قرار ندارند , این شیوه کاملا مناسب برای پردازش به کمک کامپیوتر و سازگار با سیستم کامپایلر هاست . در این شیوه هر عملگر بعد از عملوندهای مربوطه ظاهر میشود . شکل زیر شکل عبارات را در دو شیوه Infix و Postfix برای درک بهتر به خوبی نشان میدهد :


2+3*4 ---> 234*+
a*b+5 ---> ab*5+
((a/(b-c+d))*(e-a)*c ---> abc-d+/ea-*c*

مشاهده میشود که در Postfix فرایند ارزیابی بواسطه اینکه دیگر نیازی به پرانتز نیست ساده تر از Infix است .
خوب ... حالا چطور باید ارزیابی بشن :
ابتدا باید توضیح بدم که چطور باید Infix را به Postfix تبدیل کرد , چرا که ما انتظار نداریم کاربر برنامه خودش زحمت تبدیل را بکشد و عبارت را حاضر و آماده و به فرم Postfix تحویل برنامه دهد !!
در فرایند این تبدیل ابتدا باید رشته حاوی عبارت از چپ به راست پویش شود و با توجه به توضیحات قبلی و نکته ای که در اول بحث اشاره شد , در این پویش هر عملوندها تا مشاهده یک عملگر به ترتیب وارد پشته میشوند , سپس عملگر نیز وارد پشته دیگر میشود (از این مرحله هم میشود صرفنظر کرد) این کار را ادامه میدهیم تا به عملگر بعدی برسیم , در این لحظه با دو حالت مواجهیم : 1. یا این عملگر نسبت به آخرین عملگری که وارد پشته کردیم اولویت بالاتر دارد 2. یا اینکه اولویتش با آخرین عملگر وارد شده برابر است .
در حالت اول نیاز به انجام هیچ کاری نیست و فقط کافیست عملگر را به هیچگونه دردسری کمافی السابق وارد پشته کنیم . اما اگر حالت دوم پیش آمد , با ید به یاد داشته باشیم که در پشته عملگرها هیچ عملگری روی عملگر دیگری که اولویتش بیشتر یا مساوی خودش است نمینشیند.
پس با این حساب باید عملگرهای داخل پشته را یکی یکی pop کنیم و چک کنیم که وضعیت عملگری که در موقعیت top پشته قرار دارد با عملگری که قصد push کردن آنرا به پشته داریم چگونه است ؟ آیا میتواند روی آن بنشیند ؟! و این عمل را تا جایی که یا شرایط محیا شود یا پشته خالی شود ادامه میدهیم . سپس عملگر را وارد پشته میکنیم . باید توجه کرد که هر جا مجبور به pop کردن عملگری از پشته شدیم , باید همزمان دو عملوند هم از پشته عملوندها pop کنیم وپس از تاثیر دادن عملگر pop شده به آن دو , نتیجه را دوباره در پشته عملوندها ذخیره کنیم .
با توجه به توضیحات داده شده در زیر یک نمونه از کلاس پشته عملگرها گذاشته شده :


class OperatorList
{
char oper;
int prcd;
public:
OperatorList *next;
OperatorList (char o='n', OperatorList *t=0): oper(o), next(t)
{
SetPrecedence();
}
char GetOperator ()
{
return oper;
}
void SetPrecedence()
{
switch (oper)
{
case'+':
case'-':
prcd=1;
break;
case'*':
case'/':
prcd=2;
break;
}
}
int precedence()
{
return prcd;
}
} *TopOperator=0;

همچنین نمونه ای از کلاس پشته عملوندها :


class NumberList
{
double num;
public:
NumberList *next;
NumberList (double n=0, NumberList *t=0): num(n), next(t){}
double GetNumber ()
{
return num;
}
} *TopNumber=0;

نمونه ای از تابعی که برای push کردن عملگری به پشته عملگرهاست :


void PushOperator (char op)
{
OperatorList *curptr=new OperatorList(op);
if (!TopOperator)
TopOperator=curptr;
else
{
while (TopOperator->precedence() >= curptr->precedence())
calculate();
curptr->next=TopOperator;
TopOperator=curptr;
}
}

در تابع بالا یک حلقه while میبینید که همانطوریکه از شرطش برمیاد , تا زمانیکه اولویت عملگر top پشته از عملگری که قصد وارد کردن آنرا به پشته داریم بزرگتر یا مساوی باشد , تابعی به نام calculate را در هر بار گردش فراخوانی میکند . تابع calculate به این شکل عمل میکند که در هر بار اجرا یک عملگر از پشته عملگرها و دو عملوند از پشته عملوندها pop میکند و عملگر را به عملوندها اثر داده و نتیجه را در top پشته عملوندها ذخیره میکند .
نمونه ای از ایت تابع به شکل زیر است :


void calculate ()
{
int temp1=PopNumber(), temp2=PopNumber();
switch (PopOperator())
{
case'+':
PushNumber(temp2+temp1);
break;
case'*':
PushNumber(temp2*temp1);
break;
case'-':
PushNumber(temp2-temp1);
break;
case'/':
PushNumber(temp2/temp1);
break;
}
}

تابعی هم برای پویش رشته ورودی ابتدایی که در مواقع لزوم توابع push و pop پشته ها را فراخوانی میکند :


void analysis (char *str)
{
for (int i=0; str[i]; i++)
{
if (str[i]>='0' && str[i]<='9')
PushNumber(StringToNumber(str, &i));
else
PushOperator(str[i]);
}
while (TopOperator)
calculate();
}

سوالی بود در خدمتم ... موفق باشید .!

MRHagh
سه شنبه 03 اردیبهشت 1387, 18:05 عصر
دوست عزیز , اول که توصیه میکنم برای برنامه های کوچکی از این دست , سعی کن کمتر Header درست کنید . چرا که اصلا مقوله Header برای توابع یا کلاسها و یا اصلا کدهای طولانی,پرحجم و پرکاربرد است که نوشتن آنها در کدهای اصلی برنامه موجب مواجهه با انبوه کدهای تکراری در برنامه و سردرگمی خود شما و کسانی که قصد تصحیح یا توسعه برنامه شما را دارند و میشود (از اینجا بود که Header متولد شد!!!!!! ) . از این نکته نباید غافل بود که ... هر چیز بجای خویش نیکوست ... حتی در لابلای کدهای شما!!!!
این class شما دقیقا چکار میکند :

class Expr{

private:

public:
virtual double eval()=0;


};

با روشی که گفته شد و پیاده سازی دقیقش , فکر نمیکنم مشکلی پیش بیاد ... کاش میگفتی اشکالاتت چی هستن و حداقل تابع Main برنامه رو به همراه Converter رشته به عددی هم که طراحی کردی میگذاشتی به هر حال این چیزها که گذاشتی فقط کدهایی هستن که علی الظاهر مشکلی هم ندارن ...

farhadamin
چهارشنبه 04 اردیبهشت 1387, 22:21 عصر
اون expression بنیادی (fundamental) به وسیله یک کلاس (class Expr). نمایش داده شده... تنها کاری که این کلاس باید انجام دهد ارزش گذاری گره هاست... این کار به وسیله یک pure virtual انجام می شود... که به این صورت هست...

virtual double eval()=0
البته بدجوری توی این برنامه موندم..

MRHagh
پنج شنبه 05 اردیبهشت 1387, 08:02 صبح
اون جوری که من میدونم , درخت ساختار مناسبی برای تحلیل عبارتها نیست چون اصلا برای عبارتهای شامل پرانتز دارای محاسبه پیچیده است و پر شدن گره ها از ترتیب معین پییروی نخواهد کرد چراکه در مثلا بک درخت عبارت ساده ضمن اینکه هیچ عملگری در برگ نیست , تمام فرزندان چپ گره ریشه (گره هایی که ریشه اولین جد آنها محسوب میشود) عملگر هستند و از این جاست که با یک پیمایش Postorder به شکل Postfix عبارت موجود در درخت دست پیدا خواهیم کرد اما در عبارتهای شامل پرانتز دیگر این ساختار به هم میخورد و شما مجبور خواهید بود به شکل ترتیبی عمل نکنید و برای عملگرهای با اولویت بالاتر که بعد از عملگرهای با اولویت پایینتر در رشته آمده اند , زودتر گره بسازید چراکه اینها باید فرزندان گره های با اولویت پایینتر باشند ولی شما که نمیتوانید رشته را به شکلی غیر ترتیبی پویش کنید . درحالی که ساختن و پر کردن درخت ها در یک برنامه معمولا از یک روال مشخص با ترتیب مشخص و عملیاتهای عموما تکراریست از این جهت است که استفاده از آن برای عباراتی که ترتیب اولویت عملگرها با مثلا پرانتزها تغییر کرده باشد , میشود گفت عملا راه حل به صرفه ای نیست ضمن اینکه ساختار درخت هم در تحلیل عبارتها به نوعی شبیه سازی همان پشته است .
استفاده از پشته هم حجم کد را کم و هم قطعا سرعت اجرای برنامه را زیاد میکند و در آن از پیچیدگی خبری نیست چون ما در همان لحظه که رشته را پویش میکنیم در همان لحظه نیز به محاسبه عبارت میپردازیم و عموما همه عملیاتهای ما همزمان و به هم پیوسته است .
کلاسهای که در دو پست قبلی به آنها اشاره کردم , کلاسهای مناسبی برای پیاده سازی پشته های پیوندی میباشند که ضمن سرعت بالا هم میتوان به صورت نامحدود به آنها عنصر اضافه کرد و هم اینکه فضای کمی از حافظه اشغال میکند (در هنگام pop گره را حذف و حافظه را به سیستم برمیگرداند). این کدها هم که نوشتید , زیاد به درد پیاده سازی درخت نمیخورد .

farhadamin
پنج شنبه 05 اردیبهشت 1387, 21:34 عصر
ببین متاسفانه... برنامه را به همون شکلی که برات نوشتم باید بنویسم...به دلیل این که این یک قسمت کوچیک یک برنامه بزرگ است.. البته تقریبا تا نصفه های برنامه را نوشته ام... (البته با توجه به حرف های شما و این که کارهای قبلی قابل استفاده در درخت نیست برنامه را عوض کردم).. برنامه را دوباره در سایت قرار می دم... البته قسمت آخرش را نتوانستم انجام بدم... که مربوط به ساختن یک تابع
virtual string toString() و پرینت برنامه هست....(به قسمتی که به صورت کامنت در مین هست و مخصوصا قسمتی که قرمز شده..توجه کنید.. که البته باید به همین صورت حفظ شود.فقط باید هدر ها را جوری طراحی کنم که کار کند).. البته همه کلاس های مربوط به تغریف علائم ریاضی شبیه هم هستند...

تابع مین..

#include "Expr.h"
#include "num.h"
#include "BinOp.h"
#include "Oprator.h"
#include <iostream>
#include <conio.h>
#include <vector>
#include <sstream>
#include <string>

using std::cout;using std::endl;

int main()
{
std::vector<Expr *> expressions;


Num num5(5);
Num num4(4);
Num num3(3);
Num num2(2);
Num num1(1);
Num num0(0);



Plus ex_plus2_5( &num2, &num5 );

Minus ex_minus( &ex_plus2_5, &num1 );

Mult ex_mul( &ex_plus2_5, &ex_minus );
expressions.push_back( &ex_mul );

Div ex_div7_5( &ex_plus2_5, &num5 );
expressions.push_back( &ex_div7_5 );

Pow ex_pow( &num5, &num2 );
expressions.push_back( &ex_pow );

Pow ex_pow2( &num1, &ex_mul );
expressions.push_back( &ex_pow2 );

Exp ex_exp( &num2 );
expressions.push_back( &ex_exp );


Sqrt ex_sqrt( &num2 );
expressions.push_back( &ex_sqrt );

Mult ex_( &ex_pow, &ex_sqrt );

expressions.push_back( &ex_ );

/*
for( int i = 0; i < expressions.size(); ++i )
cout << expressions[i]->toString() << " = " << expressions[i]->eval() << endl;
Div ex_dbz( &num2, &num0 );
try{
cout << ex_dbz.toString(); cout.flush();
ex_dbz.eval();
}
catch (std::domain_error ex) {
cout << "Exception: " << ex.what() << endl;
*/



_getch();
return 0;
}
دقیقا قسمتی که به صورت کانت درآمد را باید در کلاس ها کاری کنم که قابل فهم باشند برای برنامه..می دونم که این تابغ tostring باید یک تابع virtual string toString() باشه . که می تواند expressions را صدا کند و فرمول ها را برگشت return دهد و همه علامت های باینری و دو تا warp در پرانتز ها.. و یک expression باید به این صورت باشد..
(2 * ((3 + 4) * pow(2, 5)))

هدر ها..که البته باز هم مجبورم همین طور جداگانه باشند...

#ifndef Num_H
#define Num_H
#include "Expr.h"
#include <string>
#include <sstream>
class Num: public Expr
{
double tal;
Expr *some_val;

public:

Num (double tal1)
{
tal=tal1;
}
double eval()
{

return tal;
}
/*std::string toString()

{
std::stringstream stream;
stream << some_val; // like cout
return stream.str(); // output a string

} */
};
#endif


#ifndef Expr_H
#define Expr_H
#include<iostream>
#include <string>

class Expr{

private:

public:
virtual double eval()=0;
//virtual std::string toString() const=0;

};


#endif



#ifndef BinOp_H
#define BinOp_H
#include "Expr.h"
#include "num.h"
#include <string>


class BinOp: public Expr
{

public:
double eval()=0;
// std::string toString()=0;
Expr *left;
Expr *right;




};



#endif



#ifndef Oprator_H
#define Opator_H
#include "BinOp.h"
#include "Expr.h"
#include "num.h"
#include <cmath>
#include <string>

class Plus: public BinOp
{
public:
std::string toString();
Plus(Expr *l, Expr *r)
{
left=l;
right=r;
}

double eval()
{
return left -> eval() + right -> eval();
}
};


class Minus: public BinOp
{
public:
std::string toString();
Minus(Expr *l, Expr *r)
{
left=l;
right=r;
}

double eval()
{
return left -> eval() - right -> eval();
}
};


class Div: public BinOp
{
public:
std::string toString();
Div(Expr *l, Expr *r)
{
left=l;
right=r;
}

double eval()
{
return left -> eval() / right -> eval();
}
};

class Mult: public BinOp
{
public:
std::string toString();
Mult(Expr *l, Expr *r)
{
left=l;
right=r;
}

double eval()
{
return left -> eval() * right -> eval();
}
};

class Pow: public BinOp
{
public:
std::string toString();
Pow(Expr *l, Expr *r)
{
left=l;
right=r;
}

double eval()
{
return pow(left-> eval(),right-> eval());
}
};


class Sqrt: public BinOp
{
public:
std::string toString();
Sqrt(Expr *r)
{

right=r;
}

double eval()
{

return sqrt(right-> eval());
}
};


class Exp: public BinOp
{
public:

std::string toString();
Exp(Expr *r)
{

right=r;
}

double eval()
{
return exp(right-> eval());
}
};
#endif

البته این جوری گذاشتم که خودتون بتونید در یک برنامه کپی کنید... من اگر دقت کرد باشید سعی کردهام قسمت آخر را ایجاد کنم (الان به صورت کامنت در کلاس هاست) اما نشده است... تابغ مین باید به همین صورت حفظ شود.... ممنون...

farhadamin
پنج شنبه 05 اردیبهشت 1387, 22:03 عصر
سلام و ممنون

فرزانه السادات موذنی
دوشنبه 17 تیر 1387, 13:23 عصر
سلام اگه می شه برنامه ماشین حساب رو به صورت کامل واسه من بنویسید ولی من از pushو popو ... چیزی سر در نمی اورم ؟

khajavi
یک شنبه 23 تیر 1387, 07:03 صبح
خانم موذنی این الگوریتمی که در بالا ارايه شد را میشه به چند روش پیاده ساری کرد. یکی از این روش ها استفاده از stack هست که برای این کار باید سرفایل <stack> را وارد برنامتون کنید.
این stack سه تابع خیلی مهم داره که با اون ها می تونیم اعمال push , pop , top را انجام بدیم.
در ضمن خود ماشین حساب هم الگوریتم های گوناگونی داره که فکر می کنم RPN معقول ترینشون باشه. RPN مخفف Reverse Polish Notation یعنی عکس نماد لهستانی که توی ساختمان های گسسته خوندیم.
راستی stack خودش یک نوع STL Container هست و برای اطلاعات بیشتر در مورد پشته:
http://www.cplusplus.com/reference/stl/
http://www.cplusplus.com/reference/stl/stack/
راستی طرز استفاده از stack به صورت زیر هست:

stack<int> number;
الان یک پشته از اعداد صحیح درست کردم

number.push( 3 );
الان عدد ۳ را وراد پشته می کنم

number.push( 7);
عدد۷ وارد پشته می شود

cout << number.top();
عدد ۷ نمایش داده می شود

number.pop();
عدد ۷ از پشته خارج می شود

cout << number.top();
عدد ۳ نمایش داده می شود

number.pop()
عدد ۳ از پشته خارج می شود

راستی اینجا را هم ببین: http://barnamenevis.org/forum/showthread.php?t=105252&page=2