關于中綴表達轉后綴表達一題我的做法及思想

2019-11-17 05:35:29

字體：大中小

來源：轉載

供稿：網友

今天做了一題的題目是這樣的:假設表達式由單子母變量和雙目四則運算算法構成。試寫一算法，將以通常書寫形式且書寫正確的表達式轉換為逆波蘭式。
下面是我做這題的思想以及具體程序,不知道大家覺得這樣做好不好,我是用遞歸做的./*思想:
1.第一個字符肯定先放到新數組.
2.假如碰到'*',或者'/'的話就先把這個符號后面的那個字符放入新數組,然后再將符號壓進去.
3.假如碰到'+','-'的話,假如下一個符號的優先級和它們一樣就用同上的方法,假如后面符號的優先級比它們
高的話就用for循環來查找下一個與它們優先級一樣的符號.假如查到的話在完成后面的符號全都放入新數組后就把這個符號放入新數組,然后再執行后面的遞歸.假如前面沒查到相同優先級符號的話就把后面的符號都放入新數組后再把這個符號放進去.做這一步中因為牽涉到后面'*','/'符號都放入后要回到原來的位置,所以就用了個yes變量來判定是否碰到這種要返回的情況,假如yes=1,就表示有這種情況,有些地方需要非凡判定.
4.假如要再加入括號的話我覺得可以再用一個類似yes類型的變量就可以完成.
*/
#define N 80
int i=0,yes=0;/*i是新數組的下標指示,yes變量用來判定'+','-'后面假如有'*','/'的情況*/
void Input(char *x);/*輸入表達式*/
void Output(char *x);/*輸出逆波蘭*/
int Fun(char *x,char *y,int n);/*遞歸函數*/
void main(void)
{
char x[N],y[N];
Input(x);
Fun(x,y,1);
Output(y);
}
int Fun(char *x,char *y,int n)/*遞歸函數*/
{int j;
if(x[n]=='/0')/*遞歸到了結束運算符*/
{
y[n]='/0';
return;
}
if(n==1)/*第一次遞歸把第一個元素放入新數組*/
y[i++]=x[0];
if(x[n]=='*'x[n]=='/')/*乘除號的判定*/
{
y[i++]=x[n+1];
y[i++]=x[n];
if(yes&&(x[n+2]=='+'x[n+2]=='-'))/*這里兩句if是用來判定yes存在的情況下的*/
{yes=0;return;}
if(yes&&x[n+2]=='/0')
return;
Fun(x,y,n+2);
}
else if(x[n]=='+'x[n]=='-')/*加減號的判定*/
{
if(x[n+2]!='*'&&x[n+2]!='/')/*直接放入新表達式的情況*/
{
   y[i++]=x[n+1];
   y[i++]=x[n];
   Fun(x,y,n+2);
}
else/*后面有乘除號的情況*/
{
   yes=1;
   y[i++]=x[n+1];
   for(j=n+2;;j+=2)
    {
    if(x[j]=='/0'x[j]=='+'x[j]=='-')
     break;
    }
   if(x[j]=='/0')/*后面的乘除直接到表達式結束的情況*/
   {
   Fun(x,y,n+2);
   y[i++]=x[n];
   y[i]='/0';
   yes=0;
   }
   else/*后面還有加減號的情況*/
   {
   Fun(x,y,n+2);
   y[i++]=x[n];
   yes=0;
   Fun(x,y,j);
   }
}
}
}
void Input(char *x)/*輸入中綴表達式*/
{
clrscr();
  gets(x);
}
void Output(char *x)/*輸出轉換后的后綴表達式*/
{
printf("Now: ");
puts(x);
getch();
}