问答题 假设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号。试编写一个判别表达式中括号是否正确配对的函数correct(exp)。其中,exp为字符串指针变量,表示被判别的表达式,若配对,返回1;否则,返回0。
【正确答案】(1)数据结构
   采用顺序表示的栈,栈中元素类型为字符
   (2)思路
   依次读入数学表达式的各个字符:遇到左括号,入栈;遇到右括号,查看栈顶元素是否与其配对。若配对,出栈;若不配对,返回0。直到把表达式全部扫描一遍。
   (3)算法
   int correct(char*exp)
   { int i=0;
     DataType x;
     PSeqStack st;
     if((st=createEmptyStack_seq())==NULL)return 0;    /*创建空栈*/
     do    /*依次读入每个字符*/
     {x=*(exp+i);
       switch(x)    /*三种括号单独配对*/
       {case'{':case'[':case'(':
           push_seq(st,x);
           break;
       case')';
           x=top_seq(st);
           if(x!='(')return 0;
           pop_seq(st);
           break;
       case')';
           x=top_seq(st);
           if(x!='[')  return 0;
           pop_seq(st);
       break;
       case'}':
           x=top_seq(st);
           if(x!='{')return 0;
           pop_seq(st);
           break;
       default:
       break;
       }
       i++;
     }while(x!='\0');
     return 1;
   }
   (4)代价分析
   程序的主体是一个do…while循环,循环的次数与表达式exp中字符的个数相同,循环体的执行时间为常量,假设字符个数为n,程序的时间代价为O(n)。
   空间代价主要用于栈,其大小取决于表达式中括号嵌套的深度,这个深度小于n/2,所以空间代价最大为O(n)。
【答案解析】