栈的定义(精)

x=Pop(S); // Pop(S)弹出除数 if(x!=0.0)

x=Pop(S)/x; //Pop(S)弹出的是被除数 else { //除数为0时终止运行 cerr<<\ exit(1); }

break;

default: //读入的必为一个浮点数的最高位数字 ins.putback(ch); //把它重新回送到输入流中 ins>>x; //从字符串输入流中读入一个浮点数 }

Push(S,x); //把读入的一个浮点数或进行相应运算 //的结果压入到S栈中

ins>>ch; //输入下一个字符，以便进行下一轮循环处理 }

if(!StackEmpty(S))

{ //若栈中仅有一个元素，则它是后缀表达式的值，否则为出错 x=Pop(S);

if(StackEmpty(S)) return x; else {

cerr<<\ exit(1); } }

else { //若最后栈为空，则终止运行 cerr<<\ exit(1); } }

此算法的运行时间主要花在while循环上，它从头到尾扫描后缀表达式中的每一个数据（每个操作数或运算符均为一个数据），若后缀表达式由n个数据组成，则此算法的时间复杂度为O(n)。此算法在运行时所占用的临时空间主要取决于栈S的大小，显然，它的最大深度不会超过表达式中操作数的个数，因为操作数的个数与运算符（假定把’@’也看作为一个特殊运算符，即结束运算符）的个数相等，所以此算法的空间复杂度也同样为O(n)。 假定一个字符串a为：

char a[30]=\

对应的中缀算术表达式为12+(3*(20/4)-8)*6@，则使用如下语句调用上述函数得到的输出结果为54。

cout<

在进行这个后缀算术表达式求值的过程中，从第四个操作数入栈开始，每处理一个操作数或运算符后，栈S中保存的操作数和中间结果的情况如图4-4所示。

图4-4 栈S中数据的变化

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

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

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

将中缀算术表达式转换为后缀算术表达式的算法描述如下： 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); }

Push(R,ch); //把ch运算符写入栈中 ch=s1[++i]; } else

{ //此处必然为数字或小数点字符 while(isdigit(ch)||ch=='.')

{ //把一个数值中的每一位依次写入到s2串中 s2[j++]=ch; ch=s1[++i]; }

s2[j++]=' '; //被转换后的每个数值后放入一个空格 } }

//把暂存在栈中的运算符依次出栈并写入到s2串中 ch=Pop(R);

while(ch!='@') { if(ch=='(') {