تبديل infix به postfix در c++

[abn.najaf]

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




کد:



#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;

}
}

[nasrin55]

برای تبدیل Infix به postfix باید رشته رو بخوانیم و به هر عملگری که می رسیم ،آن را در پشته ذخیره کنیم مگر در هنگامی که عملگر بالای پشته اولویت بالاتری داشته باشد، ارقام نیز باید به ترتیب باید در postfix تکرار شوند.
مثلا رشته ساده a + b را trace کنید: در حلقه for رشته رو یکی یکی می خواینم و جلو می رویم : طبق شرط default حرف a عینا در محل 0ام رشته postfix قرار می گیره، پس از اون به عملگر + می رسیم که آن روی پشته می گذاریم، سپس به b می رسیم که در محل 1ام رشته postfix ذخیره میشه، حلقه while نیز عملگرهای داخل پشته را برمیدارد و در رشته postfix می گذاریم در نهایت داریم:
ab+

حالا اگر رشته infix ما شامل a + b * c رشته postfix طبق مراحل زیر ساخته می شود: دقت کنید که در این رشته به دلیل بالا بودن اولویت ضرب نسبت به + باید ابتدا عبارت b*c حساب شود و سپس با a جمع می شود.


postfix : a - stack:
postfix : a stack:+
postfix : ab stack:+*
postfix: abc stack:+*
postfix:abc* stack:+
postfix: abc*+ stack:


نمی دونم واضح توضیح دادم یا نه، ولی باید trace کنید تا یادتون بمونه به جای اینکه الگوریتم رو حفظ کنید.

[مسعود اقدسی فام]

در ادامه‌ی توضیحات دوستمون

چهار تابع


char pop(void);

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



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


int prio(char);


عدد اولویت هر عملگر رو مشخص می‌کنه که با استفاده از این اعداد برنامه ترتیب محاسبه رو رعایت می‌کنه. البته تاجایی که می‌دونم + و - یه اولویت رو دارن و * و / هم یه اولویت.

[abn.najaf]

nasrin55 , مسعود اقدسی فام
تشکر خیلی عالی بود، متوجه موضوع شدم

[abn.najaf]

در ادامه‌ی توضیحات دوستمون

چهار تابع


char pop(void);

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



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


int prio(char);


عدد اولویت هر عملگر رو مشخص می‌کنه که با استفاده از این اعداد برنامه ترتیب محاسبه رو رعایت می‌کنه. البته تاجایی که می‌دونم + و - یه اولویت رو دارن و * و / هم یه اولویت.




اره منم تعجب کردم ولی چیزی که هست درست جواب میده...البته اگر مساوی باشه مقدار + و - رو تست نکردم ببینم اون جوری جواب چی در میاد

[abn.najaf]

دوستان ببینید من اشتباه می کنم یا برنامه اشتب جواب میده
infix :1+(2*3)/2

postfix :

+/2*123
ولی برنامه برای پسوندی این رو میزنه
+*/1232

[مسعود اقدسی فام]

عدد اولویت +‌ و -‌ و اولویت * و / رو یکی کنید و امتحان کنید.

[abn.najaf]

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

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




void infix_To_Postfix()
{
for (i = 0; i < infix.Length; i++)
{
if (infix[i] == "(")
push("(");










else if (infix[i] == ")")
{
while (stk[top] != "(")
postfix[j++] = pop();


if (stk[top] == "(")
top--;
}










else if (infix[i] == "/" || infix[i] == "*" || infix[i] == "-" || infix[i] == "+")
{
if (empty() != 1)
{
if (prio(infix[i]) > prio(stk[top]))
push(infix[i]);
else
{
postfix[j++] = pop();
push(infix[i]);
}
}
else
push(infix[i]);
}










else
postfix[j++] = infix[i];
}






while (empty() != 1)
postfix[j++] = pop();
}






//// pop opertation



string pop()
{
if (empty() != 1)
return stk[top--];
else
return "null";
}









//// push operation


void push(string ch)
{
if (full() != 1)
stk[++top] = ch;
else
textBox1.Text = "بیشتر از حد مجاز مقدار دهی کرده اید ";
}
//// overflow


int full()
{


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


}


//// underflow


int empty()
{


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


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


int prio(string ch)
{
switch (ch)
{
case "(":
return 1;
case "-":
return 2;
case "+":
return 2;
case "*":
return 4;
case "/":
return 4;
case "^":
return 6;
}
return 0;
}





}