برنامه عبارات infix به postfix يكي از برنامه هاي معروف در درس ساختمان داده ها است . معمولا نمونه ساده اين برنامه در ساختمان داده ها آموزش داده ميشه و تمرين و آموزش بسيار مناسبي براي كار با ساختمان داده Stack يا همون پشته هستش ! واسه فهم اين مسله بايد با درس ساختمان داده ها آشنا باشي و پشته رو خيلي خوب بشناسي و بتوني اونو با آرايه شبيه سازي كني .
حالا اين عبارات infix يعني چي ؟؟ عبارات infix همون عبارتهاي رياضي هستش كه ما در زبان هاي مختلف برنامه نويسي براي محاسبه يه مقدار بكار مي بريم . اگه بخوام ساده تر بگم يعني اينكه هر وقت شما يه عبارت رياضي رو به فرمي بنويسي كه كامپايلر اون زبان برنامه نويسي اونو بفهمه اون عبارت ميشه عبارات infix . بطور كل يعني عبارتي كه عملگر ها بين عملوند ها قرار دارند و ما برنامه نويس ها اونو توي اديتور زبان مينويسيم !
نمونه :
کد:
هدف از تبديل عبارات infix به postfix در طراحي كامپايلر ها و Parser هاي كد كاربرد بسيار زيادي داره . مثلا كامپايلر چطور ميفهمه كه عبارت رياضي اي كه شما نوشتي و شامل پرانتز و توابع تو در تو هستش رو چطور بايد مجاسبه كنه !؟! ابتدا اونو از عبارات infix به postfix تبديل ميكنه و بعد واسش كد ماشين توليد ميكنه و يا توي مفسر ها اونو مستقيم محاسبه ميكنه و نمايش ميده . :roll:
اما عبارات postfix عبارتي هستش كه نسبت به تقدم عملگرها عملوند ها چيده ميشن . مثال postfix بالا ميشه ( با در نظر گرفتن تقدم عملگر ها ) :
کد:
براي توليد اون از الگوريتم زير استفاده ميشه :
از عبارات 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;
}
}
اين برنامه عملگر توان ( مثل بيسيك با ^ در نظر گرفتم ) رو هم به عنوان يك عملگر محسوب ميكنه !
الگوریتم تبدیل postfix به infix و بالعکس + سورس برنامه
پاسخ با نقل قول
نوشته اصلی توسط emprator_01
