解码

腾讯在线笔试题解答

小Q想要给他的朋友发送一个神秘字符串，但是他发现字符串的过于长了，于是小Q发明了一种压缩算法对字符串中重复的部分进行了压缩，对于字符串中连续的m个相同字符串S将会压缩为m|S，例如字符串ABCABCABC将会被压缩为[3|ABC]，现在小Q的同学收到了小Q发送过来的字符串，你能帮助他进行解压缩么？

#include <iostream>
#include <stack>
#include <string>
#include <sstream>
using namespace std;

class Solution {
public:

    stack<string> str_src;
    stack<int> counts_src;

用于装载数据

     Solution() {};
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @return string字符串
     */
    string compress(string str) {
        // write code here
        int ninit = 0;
        string sinit = "";
        str_src.push(sinit);
        counts_src.push(ninit);

头节点初始化

        int length = str.length();
        int ptr = 0;
        string res, in;

        while (ptr < length) {
            in.clear();
          /*  if (str[ptr] == ']')
            {
                int t = counts_src.top();
                string s = str_src.top();
                string te;
                counts_src.pop();
                str_src.pop();
                string f = str_src.top();
                str_src.pop();
                for (int p = 1; p < t; p++)
                {
                    te += s;
                }
                f += te;
                str_src.push(f);
            }*/

获取字符串中的数字

          if (str[ptr] == '[') {
              ptr++;
              while (str[ptr] != '|') {
                  in += str[ptr];
                  ptr++;
              }
              stringstream ss;
              int counts;
              ss << in;
              ss >> counts;
              counts_src.push(counts);   //  插入

              in.clear();
              ptr++；
              // ------------------------------
              获取字符串
              while (str[ptr] != '[' && str[ptr] != ']') {
                  in += str[ptr];
                  ptr++;
              }
              //=======================
              插入
              str_src.push(in); 

              in.clear();

              if (str[ptr] == '[')
                  continue;
              else {
                  //===============================
                  重复指定次数的字符串并插入
                  while (str[ptr] == ']') {
                     
                      int t = counts_src.top();
                      counts_src.pop();
                      string s, temp;
                      temp = str_src.top();
                      str_src.pop();

                      for (int i = 0; i < t; i++) {
                          s += temp;
                      }
                      temp = str_src.top();
                      str_src.pop();
                      temp += s;
                      str_src.push(temp);
                      ptr++;
                  }
              }



          }
          else {
          //=========================================
          首次读入的字符非“ [ ”，小心结尾
              while (str[ptr] != '[' && str[ptr] != ']' && str[ptr] !='\0') {
                  in += str[ptr];
                  ptr++;
              }
              string tem = str_src.top();
              str_src.pop();
              tem += in;
              str_src.push(tem);
              if (str[ptr] == ']')
                  ptr++; 		//		加一防止死循环
            

          }


      }

      if (str_src.size() == 1)
          return str_src.top();
      else {
      //================================
      以】结尾的输入字符都要经过此步骤
          int si = counts_src.size();
          si--;
          while (si > 0) {
              string lstr = str_src.top(), te;
              int lcount = counts_src.top();
              str_src.pop();
              counts_src.pop();
              for (int index = 0; index < lcount; index++) {
                  te += lstr;
              }
              te = str_src.top() + te;
              str_src.pop();
              str_src.push(te);
              si--;
          }
          return str_src.top();
      }

      
      
  }
};