数据结构实验题--判断入栈出栈操作序列是否合法-白红宇

数据结构实验题--判断入栈出栈操作序列是否合法

阅读量：4613 次

发布时间：2019-06-09

本文共 1030 字，大约阅读时间需要 3 分钟。

假设以I和O分别代表入栈和出栈操作，设计一个算法判断任一给定的栈操作序列是否合法。（例如：IOIOIIOOIO）

算法的设计思想：依次扫描出栈入栈操作序列，每扫描至一个位置，需检查出栈次数是否大于入栈次数，若大则非法。

扫描结束后，再检查出栈次数与入栈次数是否相等，若不相等，则非法。

C代码如下：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6  7 char s[1000]; 8  9 /*10  * 判断一组入栈出栈操作序列是否合法的算法11  *12  **Tue Sep 17 2013 wuyudong 
          
           13 */14 15 /**16 *Judge - 判断函数17 *@str : 一组入栈出栈操作序列，默认为字符型18 *19 */20 bool Judge(char *str)21 {22 int i, I_count, O_count; 23 i = I_count = O_count = 0;24 25 while (str[i] != '\0') {26 switch (str[i]) {27 case 'I': 28 I_count++;29 break;30 case 'O':31 O_count++;32 if (O_count > I_count) {33 printf("序列非法！\n"); return false;34 }35 break;36 default:37 break;38 }39 i++;40 }41 if (I_count != O_count) {42 printf("序列非法\n");43 return false;44 } else {45 printf("序列合法\n");46 return true;47 }48 }49 50 int main()51 {52 while (gets(s)) {53 Judge(s);54 }55 return 0; 56 }