3.2.4 表达式求值问题

算法 算法3.2
　　void transform(char suffix[], char exp[] ) {
　　// 从合法的表达式字符串 exp 求得其相应的后缀式 suffix
　　InitStack(S); Push(S, # );
　　p = exp; ch = *p;
　　while (!StackEmpty(S)) {		      
  　　　if (!IN(ch, OP)) Pass( suffix, ch);　// 直接发送给后缀式
　　　else {
　　　　switch (ch) {
　　　　　case ( : Push(S, ch); break;
　　　　　case ) : {
　　　　　　Pop(S, c);
　　　　　　while (c!= ( )
　　　　　　{ Pass( suffix, c); Pop(S, c) }
　　　　　　break; }
　　　　　defult : {		   　　OP 为运算符的集合，若 ch 是运算符，则函数 IN(ch,OP) 的值为"TRUE"。
　　函数 Pass(suffix,ch) 的功能是将字符 ch 复制到数组 suffix 中。
　　从"("到")"构成一个表达式。
　		  
  　　　　　　while(!Gettop(S, c) && ( precede(c,ch)))
　　　　　　{ Pass( suffix, c); Pop(S, c); }
　　　　　　if ( ch!= # ) Push( S, ch);
　　　　　　break;
　　　　　} // defult
　　　　} // switch
　　　} // else
　　　if ( ch!= # ) { p++; ch = *p; }
　　} // while
　} // transform		   　　若c(栈顶运算符)的优先数大于或等于ch(当前运算符)的优先数，则函数precede(c,ch)值为"TRUE"。

　
　　学员可以在表达式的算法演示中的对话框中输入你想观察的表达式。动画

　　算法的时间复杂度为O (n)，其中 n 为表达式字符串的长度。