《数据结构与算法 C语言版》—— 3.2栈的应用举例

本节书摘来自华章出版社《数据结构与算法 C语言版》一 书中的第3章，第3.2节，作者：徐凤生，更多章节内容可以访问云栖社区“华章计算机”公众号查看。

3.2栈的应用举例

3.2.1数制转换

十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理：N=(N div d)×d+N mod d(其中，div为整除运算，mod为取余运算)例如：(1348)10=(2504)8，其运算过程如下：

NN div 8 N mod 8

13481684168 21021 252 02由于上述计算过程是从低位到高位顺序产生八进制数的各位数位，而一般来说，打印输出是从高位到低位进行，恰好和计算过程相反。因此，若将计算过程中得到的八进制数的各位按顺序进栈，则按出栈序列打印输出的即为与输入对应的八进制数。算法描述如下：

void conversion(){ SqStack s; int N,e; InitStack(s); scanf("%d",&N); while(N){ Push(s,N%8); N=N/8; } while(!StackEmpty(s)){ Pop(s,e); printf("%d",e); } }//conversion

3.2.2括号匹配的检验

假设在表达式中(［］())或［(［］［］)］等为正确的格式，(［()］或(()))均为不正确的格式，则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例如，考虑下列括号序列：［ ( ［ ］ ［ ］ ) ］12345678当计算机接受了第一个括号之后，它期待着与其匹配的第八个括号出现，然而等来的却是第二个括号，此时第一个括号“［”只能暂时靠边，而迫切等待与第二个括号相匹配的第七个括号“)”的出现，类似地，因等来的是第三个括号“［”，其期待匹配的程度较第二个括号更为急迫，则第二个括号也只能靠边，让位于第三个括号，显然第二个括号的期待急迫性高于第一个括号；在接受了第四个括号之后，第三个括号的期待得到满足，消解之后，第二个括号的期待匹配就成为当前最急迫的任务了，……，依此类推。可见，这个处理过程与栈的特点相吻合。如果在上述过程中，到来的右括号不是所期待的，或直到结束所期待的括号也没有到来，则说明括号不匹配。实现括号检验算法的设计思想是：设置一个栈，凡出现左括号，则进栈；凡出现右括号，首先检查栈是否为空，若栈为空，则表明该右括号多余，否则和栈顶元素比较，若相匹配，则左括号出栈，否则表明不匹配；表达式检验结束时，若栈为空，则表明表达式中匹配正确，否则表明左括号多余。算法描述如下：

int matching(char exp［］){//括号的匹配 int state=1,i=0; char e; SqStack s; InitStack(s); while(i<int(strlen(exp))&&state){ switch(exp［i］){ case '(': { Push(s,exp［i］); i++; break; } case ')': { if(!StackEmpty(s)&&GetTop(s)=='('){ Pop(s,e); i++; } else state=0; break; } }//switch }//while if(StackEmpty(s)&&state)return OK; else return ERROR; }

为了简便起见，在这里表达式中只有圆括号，定义ElemType为char类型。

3.2.3表达式求值

表达式求值是程序设计语言编译中一个最基本的问题。它的实现也要用到栈。下面的算法是用算符优先算法对表达式求值。表达式是由运算对象、运算符和括号组成的有意义的式子。从运算对象的个数上分，运算符分为单目运算符和双目运算符；从运算类型上分，它分为算术运算、关系运算和逻辑运算。在此仅限于讨论只含有“+”、“-”、“*”、“/”、正整数和圆括号的合法数学表达式。如果限于二元运算符的表达式定义为：表达式=(操作数)+(运算符)+(操作数)，则该表达式有以下三种标识方法：设Exp=S1+OP+S2，则称OP+S1+S2为前缀表示法(也称为波兰表达式)，S1+OP+S2为中缀表示法，S1+S2+OP为后缀表示法(也称为逆波兰表达式)。例如，Exp=ab+(c-d/e)f，则其前缀表达式为+ab-c/def，中缀表达式为ab+(c-d/e)f，后缀表达式为abcde/-f+。通过对算术表达式的以上三种标识方法的分析，我们可以得出以下结论。1）操作数之间的相对次序不变。2）运算符的相对次序不同。3）中缀表达式中不能丢失括号信息，否则将导致运算的次序不确定。其运算规则是：先乘除，后加减；同级运算，从左到右进行；先括号内，后括号外。4）前缀表达式中已经考虑了运算符的优先级，没有括号，只有操作数和运算符。其运算规则为：连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式。5）后缀表达式也已经考虑了运算符的优先级，没有括号，只有操作数和运算符。其运算规则为：运算符在式中出现的顺序恰为表达式的运算顺序，每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式。下面给出中缀表达式和后缀表达式的求值算法。(1)中缀表达式求值要把一个表达式翻译成一个正确求值的机器指令序列，或直接对表达式(即中缀表达式)求值，首先要能够正确解释表达式。例如，要对算术表达式4+2*3-10/5求值，依据中缀表达式求值的运算规则，这个算术表达式的计算顺序为4+2*3-10/5=4+6-10/5=4+6-2=10-2=8

算符优先的算法就是根据这个运算优先关系的规定来实现对表达式的编译或解释执行的。我们把运算符和界定符(左右括号和表达式结束符等)统称为算符，它们构成的集合记为OP。根据上述三条规则，可以得出算符间的优先关系如表31所示。

表31中，+、-、*和／为θ1时的优先级均低于“(‘但高于’)”，当θ1=θ2时，约定θ1的优先性高于θ2的优先性，“#”是表达式的结束符。为了算法的简洁，在表达式的最左边也虚设一个“#”构成表达式的一对括号。表31中的“(‘=’)”表示左右括号相遇时，括号内的运算已经完成。同理，“#”=“#”表示整个表达式求值完毕。“)”与“(”、“#”与“)”、“(”与“#”之间无优先关系，这是因为表达式中不允许它们相继出现，一旦遇到这种情况，则可以认为出现了语法错误。在下面的讨论中，我们假定所输入的表达式不会出现语法错误。为了实现算符优先算法，可以使用两个工作栈。一个称为OPTR，用以寄存运算符；另一个称为OPND，用以寄存操作数或运算结果。算法的基本思想是：1）首先置操作数栈为空栈，表达式终止符“#”为运算符栈的栈底元素。2）依次读入表达式exp中的每个字符，若是操作数则进OPND栈，若是运算符，则和OPTR栈的栈顶运算符比较优先级后作相应操作，直至整个表达式求值完毕。求值算法描述如下：

int EvaluateExpression(char *exp){ OPTRStack OPTR; OPNDStack OPND; char theta,x; int a,b,d=0; InitStack(OPTR); Push(OPTR,'#'); InitStack(OPND); while((*exp!='#')||(GetTop(OPTR)!='#')){ if(*exp>='0'&&*exp<='9'){ do{//不是运算符,则处理连续出现的数字 d=10*d+*exp-'0'; exp++; }while(*exp>='0'&&*exp<='9'); Push(OPND,d);//操作数进栈 }/if else{ d=0; switch(Precede(GetTop(OPTR),*exp)){ case '<'://栈顶元素优先级低 Push(OPTR,*exp); exp++;//继续扫描后序字符 break; case '='://脱括号并接受下一个字符 Pop(OPTR,x); exp++;//继续扫描后序字符 break; case '>' : Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a); switch(theta){ case '+':Push(OPND,a+b);break; case '-':Push(OPND,a-b); break; case '*':Push(OPND,a*b);break; case '/':Push(OPND,a/b);break; }//switch break; }//switch }//else default:printf("表达式不合法。\\n");exit(OVERFLOW); }//while return Gettop(OPND); }

其中，判定运算符优先级的函数的定义如下：char Precede(char ch1,char ch2){char OP［］="+-*/()#";//算符集合char tab［7］［8］={//运算符的优先级

">><<<>>", ">><<<>>", ">>>><>>", ">>>><>>", "<<<<<= ", ">>>>>>", "<<<<<=", }; for(int i=0;i<7;i++)if(OP［i］==ch1)break; for(int j=0;j<7;j++)if(OP［j］==ch2)break; return tab［i］［j］; }

对算术表达式3*(7-2)求值的操作过程如表32所示。

(2)后缀表达式求值后缀表达式求值的具体做法是：只使用一个对象栈，当从左向右扫描表达式时，每遇到一个操作数就送入栈中保存，每遇到一个运算符就从栈中取出两个操作数进行当前的计算，然后把结果再入栈，直到整个表达式结束，这时送入栈顶的值就是结果。利用后缀表达式求值，首先要将表达式转化为后缀表达式，然后对后缀表达式求值。由于每个运算符的运算次序要由它之后的一个运算符来确定，在后缀表达式中，优先级高的运算符领先于优先级低的运算符。所以，从原表达式求得后缀表达式的规律为：1）设立暂存运算符的栈；2）设表达式的结束符为“#”，预设运算符栈的栈底为“#”；3）若当前字符是操作数，则直接发送给后缀表达式；4）若当前运算符的优先级高于栈顶运算符，则进栈，否则，退出栈顶运算符发送给后缀表达式；5）“(”对它之前和之后的运算符起隔离作用，“)”可视为自相应左括号开始的表达式的结束符。算法描述如下：

void transform(char suffix［］,char exp［］){//将表达式转化为后缀表达式 OPTRStack OPTR; int i=0; char ch; InitStack(OPTR); Push(OPTR,'#'); while(*exp!='#') if(*exp>='0'&&*exp<='9'){ do{//不是运算符,则处理连续出现的数字 suffix［i++］=*exp; exp++; }while(*exp>='0'&&*exp<='9'); suffix［i++］='$';//操作数之间的间隔符 } else{ switch(*exp){ case'(':Push(OPTR,*exp);break; case')': Pop(OPTR,ch); while (ch!='('){suffix［i++］=ch;Pop(OPTR,ch);}; break; default: while(Precede(GetTop(OPTR),*exp)!='<'){Pop(OPTR,ch);suffix［i++］=ch;} Push(OPTR,*exp); break; } exp++; }//else while(!StackEmpty(OPTR)){Pop(OPTR,ch);suffix［i++］=ch;} }//CrtExptree

下面是后缀表达式求值的算法，在下面的算法中假设每个表达式是合乎语法的，并且假设后缀表达式以‘#’为结束字符。

int calcul_exp(char *suffixexp){//本函数返回后缀表达式的运算结果 int a,b,c,result,d; OPNDStack OPND;InitStack(OPND); while(*suffix!='#'){ d=0; if(*suffix>='0'&&*suffix<='9'){ while(*suffix!='$'){//不是运算符,则处理连续出现的数字 d=10*d+*suffix-'0'; suffix++; } Push(OPND,d);//操作数进栈 suffix++; } else{ Pop(OPND,b);Pop(OPND,a);//取出两个运算量 switch(*suffix){ case '+':c=a+b;break; case '-':c=a-b;break; case '*':c=a*b;break; case '/':c=a/b;break; } Push(OPND,c); suffix++; } } Pop(OPND,result); returnresult; }

3.2.4求命题公式的真值

利用计算机求命题公式真值的关键是：1）给出命题变元的每一组赋值；2）计算命题公式在每一组赋值下的真值，其计算类似于中缀表达式的求值。为了程序实现的方便，约定命题变元只用一个字母表示，非、合取、析取、条件和双条件联结词分别用！、&、|、－、＋来表示。设定两个全局变量：字符数组myopnd［10］和整型数组A［1024］［11］，分别存储命题公式中的命题变元和命题公式的真值表。全局变量n表示命题公式的变元数，m为其对应的赋值数。这里，假定命题公式中最多有10个命题变元。对于含n个命题变元的命题公式，数组A的前n列存储命题变元的赋值，第n+1列存储命题公式的真值。真值表中命题变元的取值具有如下规律：每列中0和1是交替出现的，且0和1连续出现的个数相同。n个命题变元的每组赋值的生成算法可基于这种思想。具体实现如下：void TrueValue(char *myopnd,int A［1024］［11］){int i,j,k,flag;for(j=0;jflag=1;k=(int)pow(2,n-j-1);for(i=0;iif(!(i%k))flag=!flag;if(flag)A［i］［j］=1;elseA［i］［j］=0;}} }求命题公式的真值，可采用与中缀表达求值相类似的算法。算符之间的优先关系如表33所示。

为实现算符优先算法，我们采用两个工作栈。一个称作OPTR，用以寄存运算符；另一个称作OPND，用以寄存操作数或运算结果。算法的基本思想是：1)首先设置操作数栈为空栈，符号“#”为运算符的栈底元素。2)求得命题公式包含的命题变元序列myopnd(按字典序排列，同一个命题变元只出现一次)。3)求得命题公式的每一组赋值。4)针对每一组赋值，计算命题公式的真值。其方法是：依次读入命题公式中的每个字符，若是命题变元，则其对应的赋值进OPND栈；若是运算符，则和OPTR栈的栈顶运算符比较后作相应操作，直至整个命题公式求值完毕。算法描述如下：void CalExpression(char *exp){ char ch;OPTRStack OPTR;OPNDStackOPND;int a,b,c,i,j,k;for(i=0,j=0;exp［i］!='#';i++)//提取命题公式中的命题变元if(!is_optr(exp［i］)){for(k=0;kif (k==j)myopnd［j++］=exp［i］; }myopnd［j］='\\0';n=j;//命题变元数m=(int)pow(2,n);//赋值数for(i=0;ifor(k=i+1;kif(myopnd［i］>myopnd［k］){ch=myopnd［i］;myopnd［i］=myopnd［k］;myopnd［k］=ch;}TrueValue(myopnd,A);InitStack(OPTR);InitSTACK(OPND);for(i=0;iPush(OPTR,'#');j=0;while(exp［j］!='#' || GetTop(OPTR)!='#' ) {if(!is_optr(exp［j］)){for(k=0;kPush(OPND,A［i］［k］);j++;}else{switch(Precede(GetTop(OPTR),exp［j］)) {case '<': Push(OPTR,exp［j］);j++; break;case '=': Pop(OPTR,ch);;j++; break;case '>': Pop(OPTR,ch);if(ch=='!'){Pop(OPND,a);if(a==1)a=0;else a=1;Push(OPND,a);}else{Pop(OPND,b);Pop(OPND,a);switch(ch) {case '+': c=(!a||b)&&(a||(!b)); break;case '-': c=(!a)||b;break;case '|': c=a||b;break;case '&': c=a&&b;break;}Push(OPND,c);}break;}}}Pop(OPND,a);A［i］［n］=a;}}其中的函数is_optr()和Precede()定义如下：int is_optr(char c){char OP［9］="+-|&!()#";for(int i=0;i<8;i++) if(c==OP［i］)return i;return 0;}char Precede(char ch1,char ch2){char OP［］="+-|&!()#";//双条件、条件、析取、合取、非char tab［8］［9］={"><<<<<>>",">><<<<>>",">>><<<>>",">>>><<>>",">>>>><>>","<<<<<<= ",">>>>>>>","<<<<<<=",};for(int i=0;i<8;i++)if(OP［i］==ch1)break;for(int j=0;j<8;j++)if(OP［j］==ch2)break;return tab［i］［j］;}

相关资源：数据结构与算法分析–C.描述（第3版）（美）Mark.Allen.Weiss