تبديل infix به postfix توسط پاسكال

[NabiKAZ]

سلام
ببخشيد ما هر وقت به مشکل بر ميخوريم سر ميزنيم .
يه سوال پاسکال هست ، اگه کسي سورسي در اين باره داره يا توضيح و کمکي از دستش بر مياد ممنون ميشم کمک کنه .
گفته که برنامه اي نويسيد که عبارات infix رو به postfix تبديل کنه . يه شرح مفصل هم داره که چيکار بايد کرد از آرايه ها و پشته استفاده ميشه.. و ميخواد که اعمال رياضي رو انجام بده ، مهمه كه توان رو هم انجام بده! فکر کردم توضيح در اين حد کافي باشه ...
راستش من که هيچي سر در نياوردم شما چي؟
البته يه سرچ كردم يه سري لينك هم ژيدا كردم ولي نميدونم كدوم ميتونه جواب باشه:

http://www.qiksearch.com/articles/cs/infix-postfix/
http://www.qiksearch.com/javascripts/inf...ostfix.htm
http://www.experts-exchange.com/Programm...94130.html
http://www.latrobe.edu.au/philosophy/phi...pprec.html
http://www.latrobe.edu.au/philosophy/phi...11pre.html
http://www.bsdg.org/SWAG/PARSING/0012.PAS.html
http://www.programmersheaven.com/zone3/cat414/16136.htm

تشکر
نبي

[Mamad2003]

نبي جان سلام

برنامه عبارات infix به postfix يكي از برنامه هاي معروف در درس ساختمان داده ها است . معمولا نمونه ساده اين برنامه در ساختمان داده ها آموزش داده ميشه و تمرين و آموزش بسيار مناسبي براي كار با ساختمان داده Stack يا همون پشته هستش ! واسه فهم اين مسله بايد با درس ساختمان داده ها آشنا باشي و پشته رو خيلي خوب بشناسي و بتوني اونو با آرايه شبيه سازي كني .

حالا اين عبارات infix يعني چي ؟؟ عبارات infix همون عبارتهاي رياضي هستش كه ما در زبان هاي مختلف برنامه نويسي براي محاسبه يه مقدار بكار مي بريم . اگه بخوام ساده تر بگم يعني اينكه هر وقت شما يه عبارت رياضي رو به فرمي بنويسي كه كامپايلر اون زبان برنامه نويسي اونو بفهمه اون عبارت ميشه عبارات infix . بطور كل يعني عبارتي كه عملگر ها بين عملوند ها قرار دارند و ما برنامه نويس ها اونو توي اديتور زبان مينويسيم !

نمونه :

کد:

A + B - C

هدف از تبديل عبارات infix به postfix در طراحي كامپايلر ها و Parser هاي كد كاربرد بسيار زيادي داره . مثلا كامپايلر چطور ميفهمه كه عبارت رياضي اي كه شما نوشتي و شامل پرانتز و توابع تو در تو هستش رو چطور بايد مجاسبه كنه !؟! ابتدا اونو از عبارات infix به postfix تبديل ميكنه و بعد واسش كد ماشين توليد ميكنه و يا توي مفسر ها اونو مستقيم محاسبه ميكنه و نمايش ميده . :roll:

اما عبارات postfix عبارتي هستش كه نسبت به تقدم عملگرها عملوند ها چيده ميشن . مثال postfix بالا ميشه ( با در نظر گرفتن تقدم عملگر ها ) :

کد:

AB+C-

براي توليد اون از الگوريتم زير استفاده ميشه :

از عبارات infix يك كاراكتر بخوان و شرط هاي زير رو روي اون چك كن :

- اگر كاراكتر ) بود اون رو به پشته اضافه كن .
-اگر عملگر بود تست كن و ببن پشته خالي هست يا نه . اگر خالي بود اون كاراكتر رو به پشته اضافه كن .
اگر پشته خالي نبود تقدم كاراكتر بالاي پشته رو با كاركتر ورودي مقايسه كن . اگر تقدم كاراكتر بالاي پشته كمتر بود كاراكتر خوانده شده رو به پشته اضافه كن . در غير اينصورت كاراكتر بالاي پشته رو حذف كن و به عبارات postfix نهايي اضافه كن و كاراكتر خوانده شده رو به پشته اضافه كن.
-اگر كاراكتر ( بود آنقدر پشته رو خالي كن و به عبارات postfix نهايي اضافه كن تا به كاراكتر ) برسي .
-اگر كاراكتر خوانده شده يه عملوند بود اونو مستقيم به عبارات postfix نهايي اضافه كن !

حالا اين مراحل رو به تعداد كاراكتر هاي موجود در عبارت infix تكرار كن تا عبارت infix تموم بشه و به انتهاي عبارت برسي . عبارت postfix شما بدست خواهد آمد !


نبي جان من چند وقت پيش كد ساده اي رو به زبان ++C واسه همين كار نوشتم . متاسفانه از پاسكال چيز زيادي نميدونم و براي همين اگر يكي از دوستان باشن كه برات تبديلش كنن به پاسكال شايد مشكلت حل بشه :

کد:

//By M.Nazemi - CSE - B.M.S college of engineering
//Infix to postfix conversion
#include <iostream.h>
#define max 30

char pop(void);
void push(char);
int Isunder(void);
int Isover(void);
int prio(char);

int top=-1,i=0,j=0;
char stk[max];
char infix[max];
char postfix[max];


void main()
{
    cout << "Please enter your expression in infix form :";
    cin >> infix ;
    for(i=0;infix[i]!='\0';i++)
    {
        switch(infix[i])
        {
            case '(' :
                
                push( '(' );
                break;

            case ')' :
                
                while(stk[top]!='(')
                    postfix[j++]=pop();
                

                if (stk[top]=='(')
                    top--;
                
                break;

            case '/':
            case '*':
            case '+':
            case '-':
         case '^':
                if (!Isunder())
                {
                    if (prio(infix[i]) > prio(stk[top]) )
                    {
                        push(infix[i]);
                        
                    }
                    else
                    {
                        postfix[j++]=pop();
                        push(infix[i]);

                    }

                }
                else
                    push(infix[i]);
                    
                break;
            
            default :
                postfix[j++] = infix[i]    ;
                
                
        }


    }

        while (!Isunder())
            postfix[j++]=pop();
        
        postfix[j]='\0';

        cout << endl << "Your postfix expression is :" << postfix << endl ;


}

//// pop opertation
char pop()
{

    if (!Isunder())
        return stk[top--];

}

//// push operation

void push(char ch)
{
    if (!Isover())
        stk[++top]=ch;
    else
        cout << "Stack is full";
}
//// overflow

int Isover()
{

    if (top == max-1)
        return 1;
    else
        return 0;

}

//// underflow

int Isunder()
{

    if (top == -1)
        return 1;
    else
        return 0;

}
/////////////////////////////
int prio(char ch)
{
    switch(ch)
    {
        case '(' :
            return 1;
            break;
        case '-' :
            return 2;
            break;
        case '+' :
            return 3;
            break;
        case '*' :
            return 4;
            break;
        case '/' :
            return 5;
            break;
        case '^':
            return 6;
            
    }
}

اين برنامه عملگر توان ( مثل بيسيك با ^ در نظر گرفتم ) رو هم به عنوان يك عملگر محسوب ميكنه !
اگر مشكلي بود من در خدمتم
موفق باشي :wink:

[NabiKAZ]

سلام ممد جان
از توضيحات كاملت ممنون . روشنم كردي . اين موضوعيه كه حدود 8 سال پيش تو شبكه هاي بي بي اس دنبال ميكردم كه اون موقع همين بحثا شد كه هيچي سر در نمي اوردم ولي الان حساب اومد دستم .
برنامت يه همچين اروري ميده .
Fatal ..\INCLUDE\IOSTREM.H 19: Error directive: Must user C++ for the type iostrem.

ضمنا برنامه رو به زبان پاسكال پيدا كردم فقط مشكلش اينه كه روي عدد كار ميكنه و با متغيير كار نميكنه .
برنامش اينجاست:
http://www.barnamenevis.org/forum/showth...post175234

به زبون سي هم اينجا هست كه كار ميكنه ولي اين بار در عمل محاسبه رو انجام نميده !
http://www.experts-exchange.com/Programm...94130.html

بازم ممنون .
نبي

[Mamad2003]

نبي جان سلام

راستش برنامه من كاملا كار ميكنه و مشكلي نداره :roll: من اينو با visual C++ 6 نوشتم و كامپايل كردم . اگه با محصولات بورلند كار ميكني خط اول رو با اين دو خط جانشين كن . احتمالا حل ميشه :

کد:

#include <iostream>
using namespace std;

راستي اگه برنامه محاسبه عبارت عددي Postfix رو هم ميخواي بايد بگم كه يه برنامه كاملا مجزاست اما كارش خيلي ساده است . كد اون رو هم واست گذاشتم كه اگه نياز داشتي استفاده كني البته فقط با چهار عمل اصلي كار ميكنه :

کد:

//By M.Nazemi - CSE - B.M.S college of engineering
//postfix expression evaluation

#include <iostream.h>
#define max 30


char pop(void);
void push(char);
int Isover(void);
int Isunder(void);
int type(char);
void eval(int,int,char);

int top=-1,i=0;
char stk[max];
int result=0;
char postfix[max];


void main()
{
    cout << "Please enter your expression in postfix form to evaluate :";
    cin >> postfix ;
    
    for(i=0;postfix[i]!='\0';i++)
    {
        switch(type(postfix[i]))
        {
            case 0 : //it is an operator
                
                push(postfix[i]-48);
                break;
//////////////////////////////////////////////////////////////////////////////////

            case 1 : //it is an operand
                
                eval((int)pop(),(int)pop(),postfix[i]);
                break;
        }
    }
                

        cout << endl << "Your postfix expression value is :" << result << endl ;


}

//// pop opertation
char pop()
{

    if (!Isunder())
        return stk[top--];

}

//// push operation

void push(char ch)
{
    if (!Isover())
        stk[++top]=ch;
    else
        cout << "Stack is full";
}
//// overflow

int Isover()
{

    if (top == max-1)
        return 1;
    else
        return 0;

}

//// underflow

int Isunder()
{

    if (top == -1)
        return 1;
    else
        return 0;

}
////////////////////////////////////////////////////////////////////////////////////////////////////////////
int type(char ch)
{
    switch(ch)
    {
        
        case '-' :
        case '+' :
        case '*' :
        case '/' :
            return 1;
            break;

        default :
            return 0;
    }
}

///////////////////////////////////////////////////////////////////////

void eval(int opr1,int opr2,char ch)
{
    
    
    switch(ch)
        {
        
            case '-' :
                result=opr1-opr2;
                break;
            case '+' :
                result=opr1+opr2;
                break;
            case '*' :
                result=opr1*opr2;
                break;
            case '/' :
                result=opr1/opr2;
                break;
        }
    
    push(result);
    


}

موفق باشي :wink:

[NabiKAZ]

فقط ميتونم بگم اي ول
روش كار ميكنم
از راهنمايي ممنونم با معرفت
نبي

[Mamad2003]

:oops: نبي جان ما چاكريم
خوشحالم مفيد واقع شد ! :)
موفق باشي :wink:

[amative]

for(i=0;infix!='\0';i++)
میشه یکمی توضیح بدین که این چه کار میکنه؟؟؟

من این پروژه رو باید تحویل بدم واستادم ازم توضیح کامل میخاد
گفته اگه بفهمم از کسی یا جایی گرفتین صفر می دم و میندازمتون
براهمین یکم ساده تر می خام و یکم توضیح توروخدا کمک کنین

تبدیل infix به postfix[/u]

---

سلام خسته نباشید این برنامه تبدیل infixبهpostfix
یکم ساده تر نمیشه
استادم ازم توضیح میخاد من من متوجه نشدم

[mehran20]

ببخشید می شه این قسمت کد رو توضیح بدید که چطوری عمل می کنه و منظورش چیه

while (!Isunder())

من فقط با این شرط مشکل دارم
یا بازم همین شرط که برای if هم گذاشتید

تابعی هم که فراخوانی می شه اینه

//// underflow

int Isunder()
{

if (top == -1)
return 1;
else
return 0;

}
/////////////////////////////

[babyy]

ببخشید می شه این قسمت کد رو توضیح بدید که چطوری عمل می کنه و منظورش چیه

while (!Isunder())

من فقط با این شرط مشکل دارم
یا بازم همین شرط که برای if هم گذاشتید

تابعی هم که فراخوانی می شه اینه

//// underflow

int Isunder()
{

if (top == -1)
return 1;
else
return 0;

}
/////////////////////////////

سلام
فکر کنم تاپیک ماله 4 سال پیش باشه !!!
---------
تو while (!Isunder())
تابع Isunder() رو فراخوانی میکنه ،
کار تابع Isunder() اینه که ببینه پسته خالی هست یا نه ، (کد رو ندیدم ، ولی top معمولا به آدرس خونه بالای پشته اشاره میکنه در حالت کلی) ؛ اگه 1- بود ، یعنی تو پشته هیچ ندارم ، و 1 بازگشت میده ، و while به کار خودش پایان میده (1 یعنی درست ، ولی while مخالفشو چک میکنه)

[mehran20]

[align=center]ببخشد ، با این که تاپیک مال خیلی وقت پیش بود اما برای من واقعا مفید بود

با این وجود که توضیح دادین اما به خوبی متوجه موضوع نشدم

مشکل من فقط درک نکردن شرطی هست که برای while گذاشته شده
چه چیزی اونجا بررسی می شه و اگه مخالف با چه چیزی بود دستورات اجرا می شه
من این رو خوب متوجه نمی شم

اگه بخوایم معادل همین دستور که در حال حاضر نوشته شده دستور دیگه ای بنویسم چی باید بنویسیم؟

ممنون

[babyy]

سلام

س . دستور while در چه شرایطی به کار خودش ادامه میده ؟؟
ج . در شرایطی که شرط داخل پرانتز هاش ، مقدار درستی رو برگردونند ،

یعنی مقدار true ؛ توجه : مقدار 1 هم true محاسبه میشه ،
حالا اینجا یکم تودرتو هستش ،

س . تو این خط :

کد:

while (!Isunder())

اول چی خونده میشه ؟؟
ج . ()Isunder
-------------
س . ()Isunder چی بر میگردونه ؟؟
ج . یا 1 ؛ یا 0
------------
فرض که 0 بر میگردونه
پس عبارتمون هست :

کد:

while(! 0)

------------
س . این علامت (!) یعنی چی ؟؟
ج . یعنی مخالف هرچی که بعدش میاد
------------
س . با توجه به اینکه 0 ، false ارزیابی میشه ، مخالفش چی میشه ؟؟
ج . ture
یعنی :

کد:

while( ! false)

که میشه نوست :

کد:

while(true)

------------
پس شرط حلقه درسته ، و حلقه آنقدر تکرار میشه ، تا شرطش غلط بشه .
------------
حالا فرض که 1 برمیگردونه ،
پس عبارت ما میشه :

کد:

while(! 1)

------------
س . این علامت (!) یعنی چی ؟؟
ج . یعنی مخالف هرچی که بعدش میاد
-----------
س . با توجه به اینکه 1 ، ture ازیابی میشه ، مخالفش چی مشه ؟؟ یعنی 1! ??
ج . یعنی غلط ؛ یا بعبارتی false .
----------
پس عبارت ما میشه :

کد:

while(! 1)

یا :

کد:

while( ! true)

یا :

کد:

while(false)

در نتیجه اینجا دیگه حلقه ادامه پیدا نمیکنه.