算法 4.5.txt

《数据结构及应用算法教程》一书的源代码。作者：严蔚敏

算法 4.5
void transform(char suffix[], char exp[] ) {
      // 从合法的表达式字符串exp求得其相应的后缀式字符串suffix，precede(a,b)
      // 判别算符法的优先程度，当a的优先数≥b 的优先数时，返回 1，否则返回0
      InitStack(S);  Push(S, '#');                   // 预设运算符栈的栈底元素为'#'
      p = exp;  ch = *p;  k=0;
      while (!StackEmpty(S)) {
        if (!OpMember(ch))   Suffix[k++] = ch;       // 操作数直接发送给后缀式
        else {
         switch (ch) {
           case '(' : Push(S, ch); break;            // 左括弧一律入栈
　         case ')' : {
             Pop(S, c);
             while (c!= '(' )            // 自栈顶至左括弧之前的运算符发送给后缀式
             { Suffix[k++] = c;  Pop(S, c) }
             break; 
            }
           default : {
             while( Gettop(S, c) && ( precede(c,ch)) ) {              
               Suffix[k++] =c;  Pop(S, c); 
              }  // 将栈中所有优先数不小于当前运算符优先数的运算符发送给后缀式
             if ( ch!= '#' )  Push( S, ch);           // 优先数大于栈顶的运算符入栈
             break;
           } // default 
         } // switch
        } // else
        if ( ch!= '#' ) ch = *++p;  
       } // while 
       Suffix[k] = '\0' ;                             // 添加字符串的结束符
} // transform