栈的应用(C语言实现)

哇,发现自己好久好久没有更了。。

我们在之前学习了栈的顺序结构以及链式结构的定义,对于栈有了一定的了解。那么为了加深对于栈的理解。我们接下来要做一些题目。

首先是经典的括号匹配问题
括号匹配问题假设表达式中包含三种括号:圆括号、方括号和花括号,它们可互相嵌套,如 ( [ { } ] ( [ ] ) )或( { ( [ ] [ ( ) ] ) } )等均为正确的格式,而 { [ ] } ) }或 { [ ( ) ] 或 ( [ ] }均为不正确的格式。
那么我们在检验算法中可设置一个栈,每读入一个括号,若是左括号,则直接入栈,等待相匹配的同类右括号;若读入的是右括号,且与当前栈顶的左括号同类型,则二者匹配,将栈顶的左括号出栈,否则属于不合法的情况。另外,如果输入序列已读尽,而栈中仍有等待匹配的左括号,或者读入了一个右括号,而栈中已无等待匹配的左括号,均属不合法的情况。当输入序列和栈同时变为空时,说明所有括号完全匹配。
(这题总让我想到一些不好的往事)。

好了有了最基础的思考,我们就可以写出代码了

void BracketMatch(char *str) 
/* str[]中为输入的字符串,利用堆栈技术来检查该字符串中的括号是否匹配*/ 
{ 
     Stack S; int i; char ch; 
     InitStack(&S); 
     For(i=0; str[i]!=’\0’; i++)   /*对字符串中的字符逐一扫描*/ 
     { 
         switch(str[i]){   
         case ‘(‘:Push(&S,str[i]); break; 
         case ‘[‘:Push(&S,str[i]); break; 
         case ‘{‘:Push(&S,str[i]); break;   
         case ‘)’: 
                  if(IsEmpty(&S)) 
                  { 
                     printf("\n右括号多余!");  
                     return;
                  } 
                  else 
                  { 
                     GetTop (&S,&ch); 
                     if(Match(ch,str[i]))  /*用Match判断两个括号是否匹配*/
                        Pop(&S,&ch);  /*已匹配的左括号出栈*/
                     else 
                     { 
                        printf("\n对应的左右括号不同类!");  
                         return;
                     } 
                  }  
                  break;  

         case ‘]’:   
                  if(IsEmpty(&S)) 
                  { 
                     printf("\n右括号多余!");  
                     return;
                  } 
                  else 
                  { 
                     GetTop (&S,&ch); 
                     if(Match(ch,str[i]))  /*用Match判断两个括号是否匹配*/
                        Pop(&S,&ch);  /*已匹配的左括号出栈*/
                     else 
                     { 
                        printf("\n对应的左右括号不同类!");  
                         return;
                     } 
                  }    
                      break;  
         case ‘}’: 
                  if(IsEmpty(&S)) 
                  { 
                     printf("\n右括号多余!");  
                     return;
                  } 
                  else 
                  { 
                     GetTop (&S,&ch); 
                     if(Match(ch,str[i]))  /*用Match判断两个括号是否匹配*/
                        Pop(&S,&ch);  /*已匹配的左括号出栈*/
                     else 
                     { 
                        printf("\n对应的左右括号不同类!");  
                         return;
                     } 
                  }  break; 

     if(IsEmpty(&S))  
         printf("\n括号匹配!"); 
     else 
     printf("\n左括号多余!"); 
} 

这个看上去很多其实很好理解。重点在与如何进行左右括号的匹配,因为匹配有顺序,所以栈可以满足这个算法。

另一个经典算法是表达式求和

表达式求值是高级语言编译的一个基本问题,是栈的典型应用实例。任何一个表达式都是由运算数(operand)、运算符(operator)和界限符(delimiter)组成的。运算数既可以是常数,也可以是被说明为变量或常量的标识符;运算符可以分为算术运算符、关系运算符和逻辑运算符三类;基本界限符有左右括号和表达式结束符等。仅讨论无括号算术表达式求值的求值问题。
由于某些运算符可能具有比别的运算符更高的优先级,因此表达式求值不可能严格地从左到右进行,比如3+4*5。这就不是从左算到右了。

那么我们可以有以下思考。
(1)规定运算符的优先级表
(2)设置两个栈:OVS(运算数栈)、OPTR(运算符栈)
(3)自左向右扫描,进行如下处理:
遇到运算数则进 OVS 栈;
遇到运算符则与 OPTR 栈的栈顶运算符进行优先级比较:
1、如果当前运算符>OPTR 栈顶运算符,则当前运算符进 OPTR 栈;
2、如果当前运算符≤OPTR 栈顶运算符,则 OPTR 退栈一次,得到栈顶运算符θ,OVS 连续退栈两次,得到运算数 a、运算数 b,对 a,b 执行θ运算,得到结果 T(i),将 T(i) 进OVS 栈。

这个用文字可能难以表示清楚,我也找到了一张图,这个图是运算A/B↑C+D*E#的表达式。

因此我们可以po出代码

int ExpEvaluation() 
/*读入一个简单算术表达式并计算其值。operator和operand分别为运算符栈和运算数栈,
OPS为运算符集合*/ 
{ 
 InitStack(&operand); 
 InitStack(&operator);  
 Push(&operator,'#');  
 printf("\n\nPlease input an expression (Ending with #) :");  ch=getchar();  
 while(ch!='#'||GetTop(operator)!='#') /* GetTop()通过函数值返回栈顶元素*/ 
 {
    if(!In(ch,OPS))   /*不是操作符,是操作数*/ 
    {  
       n=GetNumber(ch);push(&operand,n); 
    } 
    else 
    switch(Compare(ch, GetTop(operator))) //比较运算符的优先级
    { 
       case '>':  Push(&operator,ch);   ch=getchar();  break;  
       case '=':  
       case '<':
                Pop(&operator,&op); 
                Pop(&operand,&b);  
                Pop(&operand,&a); 
                v=Execute(a,op,b);  /* 对a和b进行op运算 */ 
                Push(&operand,v); break; 
   } 
} 
 v=GetTop(operand); return (v); 
} 

也就是通过不断的while循环来找到有限算的表达式。