括号嵌套问题（建议收藏）

目录

一.字符串解码

二.压缩算法

三.括号的得分

---

本篇文章主要给大家带来这个括号嵌套问题的解法，对于这种括号嵌套问题可能很多老铁都是非常的头痛。下面给大家带来这一类题目的通解

 下面我们来看看第一题字符串解码：

一.字符串解码

1.对应letecode链接：

394. 字符串解码 - 力扣（LeetCode）

2.题目描述：

3.解题思路：

遍历字符串：

• 如果当前字符为数字，即'0' <= s[i] <= '9'将该数字加到子字符串要重复的次数num中去因为数字可能有多位，因此注意原num要先乘以10再加上新加入的数字。

• 如果当前字符为左括号，即s[i] == '['进行递归，注意每次递归时num都重新赋值过递归的返回值为当前已遍历到的索引i和子字符串ans拿到返回值后将ans乘以num后加到res中，并重置num。

• 如果当前字符为右括号，即s[i] == ']'返回当前索引i以及在当前递归层的循环过程中生成的子字符串res

• 如果当前遍历到的是字母直接加入到答案中

下面以"3[a]2[bc]"为例：

 首先遇到3是一个数字将其放入num当中即可：

下面来到这个左括号进行递归调用从左括号的下一个问题开始进行调用

此时新的递归调用函数来到了a位置 将其加入到ans当中

 然后继续往下面进行遍历来到了右括号此时本次递归结束告诉调用它的地方本次递归的结果和遍历到了那个位置

收到了递归完的结果后使用num进行结果的累加并将num置为0从递归返回的下一个位置开始计算。下面的就不再重复其实都是一样的逻辑。

4.对应代码：

class Solution {
  public:
    struct Info {
        Info(string a, int s) {
            ans = a;
            stop = s;
        }
        string ans;
        int stop;
    };
    string decodeString(string s) {
        return process(s, 0)->ans;
    }
    Info* process(const string& str, int index) {
        string ans;//记录答案
        int num = 0; //记录出现的次数
        while (str[index] != ']' && index < str.size()) {
            if (isalpha(str[index])) {//字母
                ans += str[index++];
                //字母直接放入答案中即可
            } else if (isdigit(str[index])) {
                //数字
                num = num * 10 + str[index] - '0';
                index++;
            } else { //遇到了'['
                Info* ret = process(str, index + 1);
                ans += addString(num, ret->ans);
                num = 0;
                index = ret->stop + 1;//从递归返回的下一个位置计算
            }
        }
        return new Info(ans, index);

    }
    string addString(int num, string str) {
        string ans;
        for (int i = 0; i < num; i++) {
            ans += str;
        }
        return ans;
    }
};

下面我们来看一道腾讯的笔试题与上题十分的类似

二.压缩算法

1.对应OJ链接：

压缩算法_腾讯2020校园招聘-后台_牛客网 (nowcoder.com)

2.题目描述：

3.解题思路

本题和上题十分类似具体请看代码：

• 如果当前字符为数字，即'0' <= s[i] <= '9'将该数字加到子字符串要重复的次数num中去因为数字可能有多位，因此注意原num要先乘以10再加上新加入的数字。
• 如果当前字符为左括号，即s[i] == '['进行递归，递归的返回值为当前已遍历到的索引i和子字符串ans拿到返回值并将其加入到当前答案中

4.对应代码：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串
     */
    struct Info
    {
      Info(const string&str,int end)
      {
          ans=str;
          stop=end;
      }
       string ans;
        int stop;
    };
    string compress(string str) {
        // write code here
       return process(str,0)->ans;
    }
    Info*process(const string&str,int index)
    {
        string ans;//记录答案
        int num=0;
        while(index<str.size()&&str[index]!=']')
        {
            if(isalpha(str[index]))
            {
                ans+=str[index++];
            }
            else if(isdigit(str[index]))
            {
                num=num*10+str[index]-'0';
                index++;
            }
            else if(str[index]=='|')
            {
                index++;
            }
            else //遇到左括号
            {
                Info*res=process(str,index+1);
                ans+=res->ans;
                index=res->stop+1;
          
            }
        }
        if(num!=0)
        {
           ans= addString(ans,num);
        }
        return new Info(ans,index);
    }
    string addString(string &str,int num)
    {
        string ans;
        for(int i=0;i<num;i++)
        {
            ans+=str;
        }
        return ans;
    }
};

三.括号的得分

1.对应letecode链接：

856. 括号的分数 - 力扣（LeetCode）

2.题目描述：

 3.解题思路：

• 遇到左括号直接调用递归函数
• ans+=max(递归函数返回的结果*2,1)
• 返回答案和计算到了那个位置

4.对应代码

class Solution {
  public:
    struct Info {
        Info(int _score, int _stop)
            : score(_score)
            , stop(_stop)
        {}
        int score;//得分
        int stop;//计算到了那个位置
    };
    int scoreOfParentheses(string s) {
        return process(s, 0)->score;
    }
    Info* process(const string& str, int index) {
        if (str[index] == ')') {//右括号直接返回
            return new Info(0, index);
        }
        int ans = 0;
        //记录得分
        while (index < str.size() && str[index] != ')') {
            Info* res = process(str, index + 1);
            ans += max(2 * res->score, 1);//进行比较
            index = res->stop + 1;//从下一个问题开始计算
            delete res;
        }
        return new Info(ans, index);

    }
};