الگوریتم تبدیل postfix به infix و بالعکس + سورس برنامه

[Borna66]

سلام
این برنامه خیلی آسونه ! اگر کمی تجربه تو C داری خیلی راحت خودت میتونید بنویسیش . اینم الگوریتمش :

- دو تا پشته در نظر میگیریم .
2- نماد های عبارت infix رو از آخر به اول بررسی می کنیم بشکل زیر :

1) اگر نماد پرانتز بسته یا عملگر بود اونو توی پشته شماره 1 میزاریم
2) اگر نماد عملوند بود در پشته شماره 2 قرار میدیم
3) اگر نماد پرانتز باز بود ، از پشته 1 دوتا نماد برمیداریم . هر کدوم از اونها که عملگر بود به پشته دوم اضافه می کنیم .


3-این عمل رو تا جایی که به اول عبارت infix برسیم تکرار می کنیم .
4- در پایان مقدار موجود در پشته دوم رو معکوس می کنیم . در این زمان به جواب prefix می رسیم .

[Borna66]

برنامه عبارات 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;

}
}



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

[emprator_01]

سلام
راستش من خوب متوجه نشدم
اگه زحمتی نیست با یه مثال مرحله به مرحله توضیح بدی ممنون میشم
مثلا عبارت پسوندی*- ab+cd رو به میانوندی

[Borna66]

سلام
راستش من خوب متوجه نشدم
اگه زحمتی نیست با یه مثال مرحله به مرحله توضیح بدی ممنون میشم
مثلا عبارت پسوندی*- ab+cd رو به میانوندی

با سلام

دوست گرامي از اين واضح تر توضيح داده شده و بيش از اين مقدور نيست

روزگار خوش