括号匹配检测:例如{ 9 * [2(x+6) ] },需要检测右边的 )、 ]、}是否与左边的括号匹配。
原理:把上述方程存入一个字符数组当中,存储完毕后遍历数组,当遇到左括号时就PUSH入栈;当遇到右括号时就POP出栈,比较此时的右括号与此时POP出栈的左括号是否匹配。
优化:利用栈的FILO特性(逆序)和数组(正序)可以实现:把上面的方程中的左括号都存入一个字符栈当中,右括号都存入一个字符数组当中,可以节约遍历存放方程的数组的时间。
typedef struct
{
DataType *base, *top;
int stacksize;
}STA;
int Match( STA *STACK, char *Str ) //定义匹配函数。char *Str 是存放方程的数组
{
int i;
int Marker = 1; //定义一个标志符
for(i = 0;Str[ i] != '\0';i++)
{
switch( Str[ i] ) //跳跃性的选择可以用siwtch()函数
{
case '(': PUSH( &STACK,Str[ i] );
break;
case '{':[ i][ i][ i] PUSH( &STACK,Str[ i] );[ i]
break;
case '[': PUSH( &STACK,Str[ i] );[ i]
break;
case ')': if( POP( &STACK ) != '(' )
Marker = 0; //如果Marker为零,此时它是括号不匹配的标志
break;
case '}': if( POP( &STACK ) != '{' )
Marker = 0;
break;
case ']': if( POP( &STACK ) != '[' )
Marker = 0;
break;
default : break;
}
if( !Marker ) break; //如果Marker有一次为0,说明已经不匹配了,下面的匹
//配已经没有必要进行了,直接跳出循环节省时间
}
if( IsEmpty(STACK) == 1 && Marker ) //考虑在没有左括号的情况下却出现了右括号的情况
return 1; //如果为1就是匹配,为0就不匹配
else
return 0;
}
这里还需要有一个模块思维:就是把一些很简单的功能分别用一个函数表示,把它封装起来。比如IsEmpty函数,可以都封装起来,这样功能就很简洁明了了。
IsEmpty(STA STACK )
{
return STACK.base == STACK.top;
}[ i] |