الگوریتم تبدیل عبارت میانوند به پیشوند

[behnam_dr]

سلام .از مدیر انجمن خواهشمندم تذکر برای تکراری عنوان کردن این مساله نفرمائید .چون هیچ کس پاسخی درست در این باره نداده لطفا یه الگوریتم صحیح رو یه نفر توضیح بده .

متشکرم

[whitehat]

من الگوریتم برای نوشتن برنامه آنرا توضیح می دهم (قبلا برنامه آن در این بخش گذاشته شده)
برای نوشتن آن شما نیاز به یک پشته (پشته A) و یک تابع عملگر دارید که آنرا بعدا توضیح می دهم، لازم به تذکر است که برای این الگوریتم چند راه حل وجود داره که ساده ترین راه حل آنرا می نویسم که از یک پشته اضافی (پشته B) استفاده می کند
--------------------------------

1- جمله میانوندی را از ورودی بخوانید
2- از انتهای رشته شروع به پیمایش کنید
3- یک کاراکتر بخوان
4- اگر به عملوند رسیدیم آنرا در پشته B اضافه (Push) می کنیم
5- والا اگر به یک عملگر رسیدیم :
1-5- اگر پشته A خالی بود عملگر را به پشته A اضافه می کنیم
2-5-اگر اولویت عملگر فعلی از اولویت عملگر بالای پشته A بیشتر بود آنرا به پشته A اضافه می کنیم
3-5-اگر اولویت عملگر فعلی از اولویت عملگر بالای پشته A کمتر بود از پشته A آنقدر Pop می کنیم تا به عملگری برسیم که اولویت آن از عملگر فعلی بیشتر باشد
6-آیا پیمایش جمله ورودی پایان یافته
1-6-خیر، اشاره گر کاراکتر را یکی کم کن و به مرحله 3 برو
2-6- بلی به مرحله بعد برو
7- اگر پشته A خالی نیست تمام عناصر آنرا Pop و به پشته B اضافه کن
8- پشته B را خالی کن و هر کاراکتر Pop شده را در خروجی درج کن
---------------------------------
تابع عملگر
-پرانتز بسته تحت هر شرایطی در پشته درج می شود یعنی اولویت آن از همه عملگر ها بیشتر است
-پرانتز باز همیشه تمام عناصر پشته را Pop می کند تا به یک پرانتز بسته برسد و بعد از آنکه پرانتز بسته pop شد به سراغ کاراکتر بعدی می رویم
-اولویت ضرب و تقسیم از جمع و منها بیشتر است
-اولویت دو عملگر یکسان مانند -+،++،--،-+،*/،//،**،*/ کمتر است یعنی مثلا + روی - یا + قرار نمی گیرد
اگر تابع عملگر را بصورت( Eval(OP1,OP2 فرض کنیم که OP1 عنصر ورودی و OP2 عنصر بالای پشته باشد آنرا می توانید به صورت زیر بنویسید


Eval(OP1,OP2)=True If OP1<OP2
Eval(OP1,OP2)=False If OP1>OP2
Eval(OP1,OP2)=False If OP1=Op2
Eval(')',OP)=False
Eval(OP,'(')=True
Eval(OP,')')=False

تابع Eval در صورتی که True بود عملیات Pop انجام می شود تا زمانیکه False شود یا رشته تمام شود و در صورتی که False باشد عمل push انجام می شود
دقت کنید که ) یا ( در پشته B درج نمی شود
این الگوریتم راه حل بازگشتی ساده دیگری نیز دارد و همینطور شما می توانید به جای استفاده از پشته دوم رشته را از انتها در زمان پردازش چاپ کنید
لطفا روش را بررسی کنید و اگر سوالی داشتید بپرسید (امیدوارم جایی اشتباه نکرده باشم :) )
موفق باشید

[عاطفهجون]

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

[konjdivar]

الگوریتمی برای تبدیل یک عبارت میانوندی به یک عبارت پیشوندی یا لهستانی میخواستم که مثلا با دریافت
a+b
عبارت ab+ را ایجاد کند و یا با دریافت


(a+b)*(c-(d/f)*h)

عبارت


ab-c*/dfh+*
را تولید کند[/quote]

[hatame mazaheri]

می شه بر نا مه ان را دباره روی سیت بگذارید متشکر

[aapalireza]

من الگوریتم برای نوشتن برنامه آنرا توضیح می دهم (قبلا برنامه آن در این بخش گذاشته شده)
برای نوشتن آن شما نیاز به یک پشته (پشته A) و یک تابع عملگر دارید که آنرا بعدا توضیح می دهم، لازم به تذکر است که برای این الگوریتم چند راه حل وجود داره که ساده ترین راه حل آنرا می نویسم که از یک پشته اضافی (پشته B) استفاده می کند
--------------------------------

1- جمله میانوندی را از ورودی بخوانید
2- از انتهای رشته شروع به پیمایش کنید
3- یک کاراکتر بخوان
4- اگر به عملوند رسیدیم آنرا در پشته B اضافه (Push) می کنیم
5- والا اگر به یک عملگر رسیدیم :
1-5- اگر پشته A خالی بود عملگر را به پشته A اضافه می کنیم
2-5-اگر اولویت عملگر فعلی از اولویت عملگر بالای پشته A بیشتر بود آنرا به پشته A اضافه می کنیم
3-5-اگر اولویت عملگر فعلی از اولویت عملگر بالای پشته A کمتر بود از پشته A آنقدر Pop می کنیم تا به عملگری برسیم که اولویت آن از عملگر فعلی بیشتر باشد
6-آیا پیمایش جمله ورودی پایان یافته
1-6-خیر، اشاره گر کاراکتر را یکی کم کن و به مرحله 3 برو
2-6- بلی به مرحله بعد برو
7- اگر پشته A خالی نیست تمام عناصر آنرا Pop و به پشته B اضافه کن
8- پشته B را خالی کن و هر کاراکتر Pop شده را در خروجی درج کن
---------------------------------
تابع عملگر
-پرانتز بسته تحت هر شرایطی در پشته درج می شود یعنی اولویت آن از همه عملگر ها بیشتر است
-پرانتز باز همیشه تمام عناصر پشته را Pop می کند تا به یک پرانتز بسته برسد و بعد از آنکه پرانتز بسته pop شد به سراغ کاراکتر بعدی می رویم
-اولویت ضرب و تقسیم از جمع و منها بیشتر است
-اولویت دو عملگر یکسان مانند -+،++،--،-+،*/،//،**،*/ کمتر است یعنی مثلا + روی - یا + قرار نمی گیرد
اگر تابع عملگر را بصورت( Eval(OP1,OP2 فرض کنیم که OP1 عنصر ورودی و OP2 عنصر بالای پشته باشد آنرا می توانید به صورت زیر بنویسید


Eval(OP1,OP2)=True If OP1<OP2
Eval(OP1,OP2)=False If OP1>OP2
Eval(OP1,OP2)=False If OP1=Op2
Eval(')',OP)=False
Eval(OP,'(')=True
Eval(OP,')')=False
تابع Eval در صورتی که True بود عملیات Pop انجام می شود تا زمانیکه False شود یا رشته تمام شود و در صورتی که False باشد عمل push انجام می شود
دقت کنید که ) یا ( در پشته B درج نمی شود
این الگوریتم راه حل بازگشتی ساده دیگری نیز دارد و همینطور شما می توانید به جای استفاده از پشته دوم رشته را از انتها در زمان پردازش چاپ کنید
لطفا روش را بررسی کنید و اگر سوالی داشتید بپرسید (امیدوارم جایی اشتباه نکرده باشم :) )
موفق باشید

سلام!
استاد گرامی! پرانتزها چی میشه؟!
چون قراره جمله‌‌ای که پرانتز داره با رعایت اولویت بی پرانتز کنه دیگه!

[ali_fbi]

سلام دوست من

ممنون از راهنمایی خوبتون

میشه یکم در مورد استفاده از پرانتز توضیح بدین ؟

اولویت پرانتز ها چطوری هست و چطور کار می کند ؟

[samiracamputer]

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

[samiracamputer]

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

[samiracamputer]

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

[miad_sayy]

سلام من این برنامه رو از همین سایت گرفتم برای محاسبه عبارت عددی هست چرا جواب نمی ده کسی میدونه مشکل چیه
#include<stdio.h>
#include<conio.h>
#define m 21
struct stack{
int mytop;
float items[m];
}
void push(stack *s,char);
void pop(stack *s,char *);
void push(stack *s,float);
void pop(stack *s,float *);
int empty(stack *s);
void popAndtest(stack *s,char *x,int *underflow);
void topAndtest(stack *s,char *x,int *underflow);
int isOperand(char);
void convert(char[],char[]);
int pred(char,char);
int isDigit(char);
float evaluate(char []);
float operate(char,float,float);
int main()
{
char infix[m],postfix[m];
int i;
clrscr();
printf("enter an infix expression:");
gets(infix);
convert(infix,postfix);
printf("Evaluation of expression is:%.2f",evaluate(postfix));
printf("postfix expression is:");
for(i=0;postfix[i];i++)
printf("%c",postfix[i]);
getch();
return 0;
}
//*****************************
void convert(char infix[],char postfix[])
{
char symbol,topsymbol;
int underflow,i,j=0;
stack s;
s.mytop=-1;
for(i=0;infix[i],i++)
{
symbol = infix[i];
if(isOperand(symbol))
postfix[j++] = symbol;
elseif(symbol == '(')
push(&s,symbol);
elseif(symbol == ')')
{
pop(&s,&topsymbol);
while(topsymbol != '(')
{
postfix[j++] = topsymbol;
pop(&s,&topsymbol);
}//end of while
}//end of else if
else
{
topAndtest(&s, &topsymbol, &underflow);
//if op1 >op2 then true
if(empty(&s)||(!pred(topsymbol,symbol)))
push(&s,symbol);
else
{
popAndtest(&s,&topsymbol,&underflow);
while(pred(topsymbol,symbol) && !underflow)
{
postfix[j++] == topsymbol;
popAndtest(&s,&topsymbol,&underflow);
}
push(&s,symbol);
}//end of else
}//end of else
}//end of for
while(!empty(&s))_
{
pop(&s,&topsymbol);
postfix[j++]==topsymbol;
}
postfix[j] ='\o';
}
//************************************
int isOperand(char symbol)
{
if(symbol >='0' && symbol <= '9')
return 1;
return 0;
}
//************************************
void push(stack *s,char x)
{
s -> items[++(s -> mytop)]=x;
}
//************************************
void pop(stack *s,char *x)
{
*x=s ->items[(s -> mytop)--];
}
//************************************
void popAndtest(stack *s,char *x,int *underflow)
{
if(empty(s))
*underflow=1;
else
{
*x= s -> items[(s -> mytop)--];
*underflow=0;
}
}
//*************************************
void topAndtest(stack *s,char *x,int *underflow)
{
if(empty(S))
*underflow=1;
else
{
*x=s -> items[s ->mytop];
*underflow=0;
}
}
//**************************************
int empty(stack *s)
{
if(s -> mytop == -1)
return 1;
else
return 0;
}
//**************************************
int pred(char op1,char op2)
{
int i,p1,p2;
/* ( + - * / % */
staticchar op[] = {'(','+','-','*','/','%','\0'};
staticint isp[] = {0,12,12,13,13,13};
for(i=0;op[i];i++)
if(op[i]==op1)
{
p1=i;
break;
}
for(i=0;op[i];i++)
if(op[i]==op2)
{
p=i;
break;
}
if(isp[p1]> = isp[p2])
return 1;
return 0;
}
//********************************
float evaluate(char postfix[])
{
float value,operand1,operand2;
char symbol;
stack s;
s.mytop = -1;
int i;
for(i=0;postfix[i];i++)
{
symbol=postfix[i];
if(isdigit(symbol))
push(&s,(float)(symbol - '0'));
else
{
pop(&s,&operand2);
pop(&s,&operand1);
value=operate(symbol,operand1,operand2);
push(&s,value);
}//end of else
}//end of for
pop(&s,&value);
return value;
}
//***********************************
int isdigit(char symbol)
{
return (symbol >= '0' && symbol <= '9');
}
//***********************************
float operate(char symbol, float operand1,float operand2)
{
switch(symbol)
{
case'+':
return operand1 + operand2;
case'-':
return operand1 - operand2;
case'*':
return operand1 * operand2;
case'/':
return operand1 / operand2;
case'%':
return operand1 % operand2;
}
}
//*************************************
void push(stack *s,float x)
{
s -> items[++(s -> mytop)]=x;
}
//*************************************
void pop(stack *s,float *x)
{
*x= s -> items[(s -> mytop)--];
}