数据结构辅导---栈和队列(2)

3. 把中缀表达式转换为后缀表达式的算法

　　 设以’@’字符作为结束符的中缀算术表达式已经保存在s1字符串中，转换后得到的后缀算术表达式拟存于s2字符串中。由中缀表达式转换为后缀表达式的规则可知：转换前后，表达式中的数值项的次序不变，而运算符的次序发生了变化，由处在两个运算对象的中间变为处在两个运算对象的后面，同时去掉了所有的括号。为了使转换正确，必须设定一个运算符栈，并在栈底放入一个非凡算符，假定为’@’字符，让它具有最低的运算符优先级，假定为数值0，此栈用来保存扫描中缀表达式得到的暂不能放入后缀表达式中的运算符，待它的两个运算对象都放入到后缀表达式以后，再令其出栈并写入到后缀表达式中。

　　 把中缀表达式转换为后缀表达式算法的基本思路是从头到尾地扫描中缀表达式中的每个字符，对于不同类型的字符按不情况进行处理。若碰到的是空格则认为是分隔符，不需要进行处理；若碰到的是数字或小数点，则直接写入到s2中，并在每个数值的最后写入一个空格；若碰到的是左括号，则应把它压入到运算符栈中，待以它开始的括号内的表达式转换完毕后再出栈；若碰到的是右括号，则表明括号内的中缀表达式已经扫描完毕，把从栈底直到保存着的对应左括号之间的运算符依次退栈并写入s2串中；若碰到的是运算符，当该运算符的优先级大于栈顶运算符的优先级（加减运算符的优先级设定为1，乘除运算符的优先级设定为2，在栈中保存的非凡运算符’@’和’(’的优先级设定为0)时，表明该运算符的后一个运算对象还没有被扫描并放入到s2串中，应把它暂存于运算符栈中，待它的后一个运算对象从s1串中读出并写入到s2串中后，再另其出栈并写入s2串中；若碰到的运算符的优先级小于等于栈顶运算符的优先级，这表明栈顶运算符的两个运算对象已经被保存到s2串中，应将栈顶运算符退栈并写入到s2串中，对于新的栈顶运算符仍继续进行比较和处理，直到被处理的运算符的优先级大于栈顶运算符的优先级为止，然后另该运算符进栈即可。

　　按照以上过程扫描到中缀表达式结束符’@’时，把栈中剩余的运算符依次退栈并写入到后缀表达式中，再向s2写入表达式结束符’@’和字符串结束符’\0’，整个转换过程就处理完毕，在s2中就得到了转换成的后缀表达式。

　　 例如，设中缀算术表达式s1为：10+(18+9*3)/15-6@，使用的运算符栈用R表示，则转换过程如下：

　　 （1）开始时存放后缀表达式的字符串s2为空，R中压入有’@’算符，它具有最低的优先级0：

　　@

　　（2）当扫描到s1中的左括号时，s2和R中的数据变化如下：

　　1 0

　　@ + (

（3）当扫描到s1中的数值3时，s2和R中的数据变化为：

　　1 0 1 8 9 3

　　@ + ( + *

（4）当扫描到s1中的右括号时，s2和R变为：

　　1 0 1 8 9 3 * +

　　@ +

（5）当扫描到s1中的数值15时，s2和R又变为：

　　1 0 1 8 9 3 * + 1 5

　　@ + /

（6）当扫描到s1中的’@’字符时，s2和R为：

　　1 0 1 8 9 3 * + 1 5 / + 6

　　@ -

1 0 1 8 9 3 * + 1 5 / + 6 - @ Ù

　　 （7）当整个处理过程结束后，R栈为空，s2为：

将中缀算术表达式转换为后缀算术表达式的算法描述如下：

　　 void Change(char* s1, char* s2)

　　 // 将字符串s1中的中缀表达式转换为存于字符串s2中的后缀表达式

　　 {

　　 Stack R; // 定义用于暂存运算符的栈

　　 InitStack(R); // 初始化栈

　　 Push(R,'@'); // 给栈底放入'@'字符，它具有最低优先级0

　　 int i,j;

　　 i=0; // 用于指示扫描s1串中字符的位置，初值为0

　　 j=0; // 用于指示s2串中待存字符的位置，初值为0

　　 char ch=s1[i]; // ch保存s1串中扫描到的字符，初值为第一个字符

　　 while(ch!='@')

　　 { // 顺序处理中缀表达式中的每个字符

　　 if(ch==' ')

　　 // 对于空格字符不做任何处理，顺序读取下一个字符

　　 ch=s1[++i];

　　 else if(ch=='(')

　　 { // 对于左括号，直接进栈

　　 Push(R,ch);

　　 ch=s1[++i];

　　 }

　　 else if(ch==')')

　　 { // 对于右括号，使括号内的仍停留在栈中的运算符依次

　　 // 出栈并写入到s2中

　　 while(Peek(R)!='(')

　　 s2[j++]=Pop(R);

　　 Pop(R); // 删除栈顶的左括号

　　 ch=s1[++i];

　　 }

　　 else if(ch=='+'ch=='-'ch=='*'ch=='/')

　　 { // 对于四则运算符，使暂存在栈中的不低于ch优先级

　　 // 的运算符依次出栈并写入到s2中

　　 char w=Peek(R);

　　 while(Precedence(w)>=Precedence(ch))

　　 { // Precedence(w)函数返回运算符形参的优先级

　　 s2[j++]=w;

　　 Pop(R); w=Peek(R);

　　 &n