括号匹配算法

father::算法 括号匹配 括号闭合 括号判断

1. 过程梗概:

1. 功能描述:

1. 检测一串字符串, 多种括号成对出现, 并返回检查结果

2. 梗概:

1. 读取字符串, 按读取顺序记录下左括号种类
2. 读取到右括号时就要判断了(右括号决定是否成对)
   1. 如果右括号读取顺序与左括号记录循序相反且对应
      1. 则ture
   2. 否则
      1. 则false

3. 算法实现技术

1. 用栈存储左括号
   1. 因为左括号输入顺序和读取顺序刚好相反

4. 算法详细描述:

1. 对每个字符遍历扫描
2. 如果为左括号
   1. 压入栈中
3. 如果为右括号
   1. 如果栈为空
      1. 则return 1 表示右括号多余
   2. 否则
      1. 与栈顶左括号比较
         1. 如果括号类型匹配
            1. 栈顶出栈
         2. 否则
            1. return 2 表示左右括号不同类
4. 如果栈为空
   1. return 0 表示括号成对存在
5. 否则
   1. return 3 表示左括号多余

2. C语言代码实现

int Match(char ch1,char ch2)
{   // 判断左括号ch1和右ch2是否匹配，匹配返回TRUE，否则返回FALSE
    switch (ch1)
    {
        case '(':if(ch2!=')')return 0;break;
        case '[':if(ch2!=']')return 0;break;
        case '{':if(ch2!='}')return 0;break;
    }
    return 1;
}
 
int BracketMatch(char *str)
{   // str[]中为输入的字符串，利用堆栈技术来检查该字符串中的括号是否匹配
    SeqStack S;  int i;  char ch;
 
    InitStack(&S);
    for (i=0; str[i]!='\0'; i++)   // 对字符串中的字符逐一扫描
    {   switch(str[i])
        {   case '(': 
            case '[': 
            case '{': Push(&S,str[i]);  break;
            case ')': 
            case ']':
            case '}': if ( IsEmpty(&S) )  return 2;
                      GetTop(&S,&ch);
                      if ( Match(ch,str[i]) )  // 用Match判断两个括号是否匹配
                          Pop(&S,&ch);         // 已匹配的左括号出栈
                      else  return 3;
        }
    }
    return ( IsEmpty(&S)? 0 : 1 ); 
}

js代码实现

• child::获取括号范围