问答题
假设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号。试编写一个判别表达式中括号是否正确配对的函数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)。
【答案解析】