括号匹配 | 字符串处理

我会带着你远行 2022-12-05 13:48 147阅读 0赞

> ## 10. 括号匹配 ##
> 
> <table> 
>  <tbody> 
>   <tr> 
>    <td>成绩</td> 
>    <td>10</td> 
>    <td>开启时间</td> 
>    <td>2020年09月10日 星期四 12:00</td> 
>   </tr> 
>   <tr> 
>    <td>折扣</td> 
>    <td>0.8</td> 
>    <td>折扣时间</td> 
>    <td>2020年09月17日 星期四 09:00</td> 
>   </tr> 
>   <tr> 
>    <td>允许迟交</td> 
>    <td>否</td> 
>    <td>关闭时间</td> 
>    <td>2020年10月10日 星期六 23:00</td> 
>   </tr> 
>  </tbody> 
> </table>
> 
> **Description**
> 
> 括号序列是由左括号“(”和右括号“)”组成的非空序列。对于一个括号序列很容易判定其合法性。比如“()”、“(())()”、“(()())”、“(()(()))”、“()()()”都是合法的，而“)”、“(”、“(()”、“(()))(”都是非法的。
> 
> 给定n个括号序列，两两配对，问最多能组成多少对合法括号序列。（每一个括号序列只能在一对中出现）
> 
> **Input**
> 
> 第一行输入整数 n 表示有 n 个括号序列，接下来n行输入n个括号序列。
> 
> **Output**
> 
> 输出一个整数，表示最大的合法括号序列对数。
> 
> **Hint**
> 
> 第一组用例可以组成2对合法括号序列，分别是“((   )())”、“(   )”。

--------------------

### 1、括号序列的简化操作 ###

本题是经典的括号匹配问题，我们先来看一个单独括号串，我们要如何判断他是匹配的呢？以括号串((()()))为例，一眼看上去他就是匹配的！那我们怎么用程序的方式去思考他？  
       不如这样：我们准备一个**只有一端开口的容器stack**，且规定这个容器我们**只能依次放入顶端，或者取出顶端**。后面你就会学到，这种容器叫做栈，是一种很常见的数据结构。下面是栈的基本操作示意图，理解这种模型就好。

![Java版-数据结构-栈| 小白程序之路][Java_-_-_]

![20200910175719429.png][]

我们下面需要通过上面这个容器来简化括号串，使得我们**简化之后得到的串，其是否匹配的结论和原串相同。**依次遍历括号串的每一个元素t，每个元素具体的操作如下（此过程不理解的话，自己手动试一试）：

*  如果容器stack最顶端的元素（stack不为空）与t匹配：将stack顶端的元素取出；
 *  如果容器stack为空或者容器stack最顶端的元素与t不匹配：将元素t放入stack顶端

遍历完成后，我们**简化后的括号串就在容器内**。**如果容器stack内为空，说明括号串本身是匹配的，否则一定是不匹配**的。

--------------------

###  2、本题思路        ###

再来看看本题的要求，我们要判断两个括号串s1、s2连起来是否能组成一个匹配的括号串。那么应该有两种情况：

*  s1、s2本身都是已经匹配的括号串，连起来肯定还是匹配的喽
 *  s1、s2本身都不是可匹配的字符串，但是他们简化后的串可以相互匹配。

这里我们重点讨论第二种情况，如果简化后的可以匹配，那么两个简化串一定是**清一色**（只能有左括号/右括号一种）的，且两个简化串的**数目相同**，元素**种类相反**。  
  
比如说s1:  )(()))可以简化为))  
比如说s2:  (()(可以简化为((  
**简化后的两串是可以匹配的，那么原串也是可以匹配的。**

--------------------

那么根据以上总结，我们整理出本题的算法：  
        对于输入的n个串s，我们一一将他们简化，并且将简化后的结果记录下来。如果为空，则记录入本身匹配串的数目；否则记录他们是几个左括号/几个右括号，数目记录到数组left、right中。（如果化简后即有左括号又有右括号，则他必不可跟任何串匹配，直接忽略掉）  
  
        题中要求每一个串只可匹配一次，left\[i\]记录了化简后长度为i个左括号的串的个数，right数组同理。那么我们最终的总匹配数应该这样计算：本身就是匹配的calc个字符串最多可以匹配成calc/2组；遍历left数组，取min（left［i］，right［i］）。

--------------------

### 3、代码实现 ###

理解了上面的思路，写代码就比较容易了。可能第一次接触栈，不知道如何将这种模型用编程来实现，下面的代码是通过一个**一维数组和移动的下标来实现的**，这是 c 代码实现栈的一种方式。其实如果是C++就更加简便了，C++的stack库中有封装好的栈，我们可以像基本数据类型（如int）一样去直接定义，然后直接使用即可。不过这个题乐学上只让交c代码，emmmm我就把它改成c贴在这了...完整代码如下：

#include <stdio.h>
    #include <string.h>
    
    #define MAX_LEN 100050
    
    
    /* 分别记录化简之后，全为左括号/右括号的串的个数，下标代表括号个数
     * 如：left[3]代表"((("有多少个，right[2]代表"))"有多少个 */
    long long left[MAX_LEN] = {0}, right[MAX_LEN] = {0};
    long long calc = 0;  //记录化简之和位空串的个数（该串化简前本身就是合法的）
    
    int match(char c1, char c2) {
        if(c1 == '(' && c2 == ')')
            return 1;
        else
            return 0;
    }
    
    /* 处理字符串s，将其化为最简形式
     * 并将最简形式记录在left/right数组中 */
    void dealStr(char s[]) {
        /* 利用栈依次考虑每一个字符
         * 最终将其最简形式留在栈内 */
        char stack[MAX_LEN];
        int top_index = -1;  //指向栈顶元素下标
        for (int i = 0; i < strlen(s); i++) {
            //当栈非空 且 栈顶与待加入元素相匹配时
            if (top_index != -1 && match(stack[top_index], s[i]))
                top_index--;  //出栈
            else
                stack[++top_index] = s[i];  //入栈
        }
        /* 处理其最简形式，进行记录 */
        //最简形式为空，本身就是匹配的
        if (top_index == -1) {
            calc++;
            return;
        }
    
        char c = stack[top_index];
        int count = top_index + 1; //记录下化简完后的栈内剩余元素
    
        while (top_index >= 0) {
            if (stack[top_index] != c)  //栈内剩余字符串不是同号的
                return;
            top_index--;
        }
    
        if (c == '(')
            left[count]++;
        else
            right[count]++;
    }
    
    
    int main() {
        int n;
        char str[MAX_LEN];
        scanf("%d\n", &n);  //一定记得吸去换行符
    
        /* 依次读入初始字符串并进行处理 */
        for (int i = 0; i < n; i++) {
            scanf("%s", str);
            dealStr(str);
        }
    
        //本身就是匹配的字符串，两两匹配
        long long ans = calc / 2;
        for (int i = 0; i < MAX_LEN; i++) {
            ans += left[i] < right[i] ? left[i] : right[i];
        }
    
        printf("%lld\n", ans);
    }

--------------------

欢迎关注个人公众号**“** **鸡翅编程 ”**，这里是认真且乖巧的码农一枚。

*---- 做最乖巧的博客er，做最扎实的程序员 ----*

旨在用心写好每一篇文章，平常会把笔记汇总成推送更新~

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70]

[Java_-_-_]: /images/20221123/10a6f7a2bbfb4bb2822665591b43fb3c.png
[20200910175719429.png]: /images/20221123/7707e3c32a894df39762c14f0d5b74a9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70]: /images/20221123/101c1026c6904dd0b953dc5cd2e846e8.png