2014年考研数据结构辅导（13）

中缀表达式转化成后缀表达式算法

void trans-post(char E[n] ,char B[n])  //中、后缀表达式转换//

{  //E[n]是中缀表达式、B[n]是后缀表达式存储的空间

  int i=0,j=0; char x; stype S;

  Clearstack(S); Push(S,‘#’)；//‘#’入栈// 

     do {

   x=E[i++] ; //扫描当前表达式分量//

       if (x=‘#’)  //到了中缀表达式最后了

while(!Emptystack(S)) //全部退栈,#和#是优先级最低的，

    B[j++]==pop(S); //所以当前栈的所有运算都要规约

  //输出栈顶运算符，并退栈直到遇见栈底的开始放进去的那个＃//

       else if (isdigit(x))

B[j++]=x;  //操作数直接输出//

   else if (x=‘)’) //遇到）那么就一定要找到（

   {

while (Getstop(S)!=‘(’)

  B[j++]=pop(S); //输出栈顶，并退栈//

pop(S); //退掉‘（’//

   }

   else   //x为运算符//

   { 

while (precede(Getstop(S), x))  //栈顶（ q1）与x比较//

B[j++]=pop(S); // q1 >=x时，输出栈顶符并退栈//

  Push(S,x); // q1 < x时x进栈//

   }

   } while (x!=’#’);

B[j]=’#’;

} //置表达式结束符//