华为OD机试：最长子字符串的长度（二）

题目描述

模拟一套简化的序列化传输方式，请实现下面的数据编码与解码过程

1.编码前数据格式为 [位置,类型,值]，多个数据的时候用逗号分隔，位置仅支持数字，不考虑重复等场景；类型仅支持：Integer / String / Compose（Compose的数据类型表示该存储的数据也需要编码）

2.编码后数据参考图示，数据区的格式是：位置#类型#长度#数据，类型存储需要编码，Integer->0；String->1；Compose->2，长度是指数据的字符长度；数据仅允许数字、大小写字母、空格。

3.输入的编码字符长度不能超过1000，一个数据的格式错误，则解析剩下数据，其他错误输出ENCODE_ERROR。

4.输入的解码字符不能超过1000，数据区异常则跳过继续解析剩余数据区，其他异常输出DECODE_ERROR。

输入描述

输入有两行：

第一行是命令，1表示编码，2表示解码

第二行输入待编码、解码的字符

数据最多嵌套10层，[1,Compose,[1,String,Second]] 为2层嵌套。

输出描述

如果输入要求是编码，则输出编码结果；

如果输入要求是解码，则输出解码结果；

当异常时输出对应的错误字符。

用例

题目解析

1.首先判断输入的命令是编码还是解码。

2.如果是编码，遍历输入的数据列表，根据数据类型进行编码，并将结果拼接成一个字符串。

3.如果是解码，遍历输入的编码字符串，根据编码规则进行解码，并将结果存储到一个列表中。

4.在编码和解码过程中，需要注意处理异常情况，如数据格式错误、编码字符长度超过限制等。

JS算法源码
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

const type2num = { Integer: "0", String: "1", Compose: "2" };
const num2type = { 0: "Integer", 1: "String", 2: "Compose" };

void (async function () {
  const command = await readline();
  const str = await readline();

  switch (command) {
    case "1":
      console.log(encode(str));
      break;
    case "2":
      try {
        console.log(decode(str));
      } catch (e) {
        console.log("DECODE_ERROR");
      }
      break;
  }
})();

function check_encode_str(str) {
  const stack = [];

  for (let c of str) {
    if (c == "]") {
      while (stack.length > 0 && stack.at(-1) != "[") {
        stack.pop();
      }

      if (stack.length == 0) {
        return false;
      } else {
        stack.pop();
      }
    } else {
      stack.push(c);
    }
  }

  return stack.length == 0;
}

function check_encoded(pos, type, data) {
  const num_regExp = /^\d+$/;
  const str_regExp = /^[0-9a-zA-Z\s]+$/;

  if (!num_regExp.test(pos)) {
    return false;
  }

  if (type2num[type] == undefined) {
    return false;
  }

  if (type == "Integer") {
    return num_regExp.test(data);
  } else if (type == "String") {
    return str_regExp.test(data);
  }

  return true;
}

function encode(str) {
  str = str.replaceAll("],[", "][");

  if (!check_encode_str(str)) {
    return "ENCODE_ERROR";
  }

  let s = str.replaceAll("[", "<").replaceAll("]", ">");

  const reg = /<([^<>]+)>/;

  let match;
  while ((match = reg.exec(s))) {
    let [pos, type, data] = match[1].split(",");

    let encodeStr = "";

    if (check_encoded(pos, type, data)) {
 
      encodeStr = [pos, type2num[type], data.length, data].join("#");
    }

    s = s.replace(match[0], encodeStr);
  }

  return s;
}

function check_decoded(pos, type, data) {
  const num_regExp = /^\d+$/;
  const str_regExp = /^[0-9a-zA-Z\s]+$/;

  if (!num_regExp.test(pos)) {
    return false;
  }

  if (num2type[type] == undefined) {
    return false;
  }

  if (type == "0") {
    return num_regExp.test(data);
  } else if (type == "1") {
    return str_regExp.test(data);
  }

  return true;
}

function decode(str) {
  let queue = str.split("#");

  const res = [];

  while (queue.length > 0) {
    if (queue.length < 4) {
      throw "DECODE_ERROR";
    }

    const pos = queue.shift();
    let type = queue.shift();
    const len = parseInt(queue.shift());

    const remain = queue.join("#");
    queue.length = 0;

    let data = remain.slice(0, len);

    if (remain.length > len) {
      queue = remain.slice(len).split("#");
    }

    if (type == "2") {
      data = decode(data);
    }

    if (check_decoded(pos, type, data)) {
   
      res.push(`[${pos},${num2type[type]},${data}]`);
    }
  }

  return res.join(",");
}

Java算法源码
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {
    static HashMap<String, String> type2num = new HashMap<>();

    static HashMap<String, String> num2type = new HashMap<>();

    static Pattern num_RegExp = Pattern.compile("^\\d+$");
    static Pattern str_RegExp = Pattern.compile("^[0-9a-zA-Z\\s]+$");


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int command = Integer.parseInt(sc.nextLine());
        String str = sc.nextLine();

        type2num.put("Integer", "0");
        type2num.put("String", "1");
        type2num.put("Compose", "2");

        num2type.put("0", "Integer");
        num2type.put("1", "String");
        num2type.put("2", "Compose");

        switch (command) {
            case 1:
                System.out.println(encode(str));
                break;
            case 2:
                try {
                    System.out.println(decode(str));
                } catch (Exception e) {
                    System.out.println("DECODE_ERROR");
                }
                break;
        }
    }

    public static boolean check_encode_str(String str) {
        LinkedList<Character> stack = new LinkedList<>();

        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);

            if (c == ']') {
                while (!stack.isEmpty() && stack.getLast() != '[') {
                    stack.removeLast();
                }

                if (stack.isEmpty()) {
                    return false;
                } else {
                    stack.removeLast();
                }

            } else {
                stack.addLast(c);
            }
        }

        return stack.isEmpty();
    }

    public static boolean check_encoded(String pos, String type, String data) {
        if (!num_RegExp.matcher(pos).find()) {
            return false;
        }

        if (!type2num.containsKey(type)) {
            return false;
        }

        if ("Integer".equals(type)) {
            return num_RegExp.matcher(data).find();
        } else if ("String".equals(type)) {
            return str_RegExp.matcher(data).find();
        }

        return true;
    }

    public static String encode(String s) {
           s = s.replaceAll("],\\[", "][");

        if (!check_encode_str(s)) {
            return "ENCODE_ERROR";
        }

         s = s.replaceAll("\\[", "<").replaceAll("]", ">");

        Pattern p = Pattern.compile("<([^<>]+)>");

        while (true) {
            Matcher m = p.matcher(s);
            if (!m.find()) break;

            String[] tmp = m.group(1).split(",");

            String pos = tmp[0];
            String type = tmp[1];
            String data = tmp[2];

            String encodeStr = "";

            if (check_encoded(pos, type, data)) {
                encodeStr = pos + "#" + type2num.get(type) + "#" + data.length() + "#" + data;
            }

            s = s.replace(m.group(0), encodeStr); 
        }

        return s;
    }

    public static boolean check_decoded(String pos, String type, String data) {
        if (!num_RegExp.matcher(pos).find()) {
            return false;
        }

        if (!num2type.containsKey(type)) {
            return false;
        }

        if ("0".equals(type)) {
            return num_RegExp.matcher(data).find();
        } else if ("1".equals(type)) {
            return str_RegExp.matcher(data).find();
        }

        return true;
    }


    public static String decode(String str) {
        LinkedList<String> queue = new LinkedList<>();
        Collections.addAll(queue, str.split("#"));

        StringJoiner res = new StringJoiner(",");

        while (!queue.isEmpty()) {
            String pos = queue.removeFirst();
            String type = queue.removeFirst();
            int len = Integer.parseInt(queue.removeFirst());

            String remain = String.join("#", queue);
            queue.clear();

            String data = remain.substring(0, len);

            if (remain.length() > len) {
                Collections.addAll(queue, remain.substring(len).split("#"));
            }

            if ("2".equals(type)) {
                data = decode(data);
            }

            if (check_decoded(pos, type, data)) {
          
                res.add("[" + pos + "," + num2type.get(type) + "," + data + "]");
            }
        }

        return res.toString();
    }
}

Python算法源码
import re

command = input()
s = input()

type2num = {"Integer": "0", "String": "1", "Compose": "2"}
num2type = {"0": "Integer", "1": "String", "2": "Compose"}

num_regExp = re.compile("^\\d+$")
str_regExp = re.compile("^[0-9a-zA-Z\\s]+$")


def check_encode_str(s):
    stack = []

    for c in s:
        if c == ']':
            while len(stack) > 0 and stack[-1] != '[':
                stack.pop()

            if len(stack) == 0:
                return False
            else:
                stack.pop()
        else:
            stack.append(c)

    return len(stack) == 0


def check_encoded(pos, typ, data):
    if not num_regExp.match(pos):
        return False

    if typ not in type2num:
        return False

    if typ == "Integer":
        return num_regExp.match(data)
    elif typ == "String":
        return str_regExp.match(data)

    return True


def encode():
    global s

  
    s = s.replace("],[", "][")

    if not check_encode_str(s):
        return "ENCODE_ERROR"

    s = s.replace("[", "<").replace("]", ">")

    p = re.compile("<([^<>]+)>")

    m = p.search(s)
    while m is not None:
        pos, typ, data = m.group(1).split(",")

        res = []

        if check_encoded(pos, typ, data):
            res.append(pos)
            res.append(type2num[typ])
            res.append(str(len(data)))
            res.append(data)

        s = s.replace(m[0], "#".join(res))  
        m = p.search(s)  

    return s


def check_decoded(pos, typ, data):
    if not num_regExp.match(pos):
        return False

    if typ not in num2type:
        return False

    if typ == "0":
        return num_regExp.match(data)
    elif typ == "1":
        return str_regExp.match(data)

    return True


def decode(string):
     queue = string.split("#")

     res = []

    while len(queue) > 0:
          pos = queue.pop(0)
        typ = queue.pop(0)
         length = int(queue.pop(0))

         remain = "#".join(queue)
        queue.clear()

         data = remain[:length]

        if len(remain) > length:
            queue = remain[length:].split("#")

        if typ == "2":
            data = decode(data)

        if check_decoded(pos, typ, data):
            res.append(f"[{pos},{num2type[typ]},{data}]")

    return ",".join(res)


def solution():
    if command == '1':
        print(encode())
    elif command == '2':
        try:
            print(decode(s))
        except:
             print("DECODE_ERROR")


solution()

C算法源码
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_SIZE 1001
#define TRUE 1
#define FALSE 0

typedef struct ListNode {
    char *ele;
    struct ListNode *prev;
    struct ListNode *next;
} ListNode;

typedef struct LinkedList {
    int size;
    ListNode *head;
    ListNode *tail;
} LinkedList;

LinkedList *new_LinkedList() {
    LinkedList *link = (LinkedList *) malloc(sizeof(LinkedList));
    link->size = 0;
    link->head = NULL;
    link->tail = NULL;
    return link;
}

void addLast_LinkedList(LinkedList *link, char *ele) {
    ListNode *node = (ListNode *) malloc(sizeof(ListNode));
    node->ele = (char *) calloc(MAX_SIZE, sizeof(char));
    strcpy(node->ele, ele);
    node->prev = NULL;
    node->next = NULL;

    if (link->size == 0) {
        link->head = node;
        link->tail = node;
    } else {
        link->tail->next = node;
        node->prev = link->tail;
        link->tail = node;
    }

    link->size++;
}

char *removeFirst_LinkedList(LinkedList *link) {
    if (link->size == 0) exit(-1);

    ListNode *removed = link->head;

    if (link->size == 1) {
        link->head = NULL;
        link->tail = NULL;
    } else {
        link->head = link->head->next;
        link->head->prev = NULL;
    }

    link->size--;

    return removed->ele;
}

int isInteger(const char *s) {
    int i = 0;
    while (s[i] != '\0') {
        if (s[i] < '0' || s[i] > '9') {
            return 0;
        }
        i++;
    }

    return 1;
}

int isValidStr(const char *s) {
    int i = 0;

    while (s[i] != '\0') {
        char c = s[i];

        int flag = (c >= '0' && c <= '9') || (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || c == ' ';

        if (!flag) {
            return 0;
        }

        i++;
    }

    return 1;
}

int check_encode_str(char *s) {
    char *pos = strstr(s, "],[");
    while (pos != NULL) {
        long long i = pos - s + 1;

        while (s[i] != '\0') {
            s[i] = s[i + 1];
            i++;
        }

        pos = strstr(s, "],[");
    }

    char stack[MAX_SIZE] = {'\0'};
    int stack_size = 0;

    int i = 0;
    while (s[i] != '\0') {

        if (s[i] == ']') {
            while (stack_size > 0 && stack[stack_size - 1] != '[') {
                stack_size--;
            }

            if (stack_size == 0) {
                return FALSE;
            } else {
                stack_size--;
            }
        } else {
            stack[stack_size++] = s[i];
        }

        i++;
    }

    return stack_size == 0;
}


void encode(char *s) {
    if (!check_encode_str(s)) {
        printf("ENCODE_ERROR\n");
        return;
    }

    while (TRUE) {
        int l = 0;
        while (s[l] != '\0' && s[l] != '[') {
       
            l++;
        }

        if (s[l] == '\0') {
            break;
        }

        int r = l + 1;
        while (s[r] != '\0') {
            if (s[r] == ']') {
                break;
            }

           
            if (s[r] == '[') {
                l = r;
            }

            r++;
        }

        char tmp[MAX_SIZE] = {'\0'};
        strncpy(tmp, s + l + 1, r - l - 1);

        char *pos = strtok(tmp, ",");
        char *type = strtok(NULL, ",");
        char *data = strtok(NULL, ",");

        int flag = TRUE;

        if (strcmp(type, "Integer") == 0) {
            type = "0";
            flag = isInteger(data);
        } else if (strcmp(type, "String") == 0) {
            type = "1";
            flag = isValidStr(data);
        } else if (strcmp(type, "Compose") == 0) {
            type = "2";
        } else {
            flag = FALSE;
        }

        if (flag) {
            flag = isInteger(pos);
        }

        char repl[MAX_SIZE] = {'\0'};

        if (flag) {
            strcat(repl, pos);
            strcat(repl, "#");

            strcat(repl, type);
            strcat(repl, "#");

            char len[10] = {'\0'};
            sprintf(len, "%lld", strlen(data));

            strcat(repl, len);
            strcat(repl, "#");

            strcat(repl, data);
        }

        char ss[MAX_SIZE] = {'\0'};
        strncat(ss, s, l);
        strcat(ss, repl);
        strcat(ss, s + r + 1);

        memset(s, '\0', MAX_SIZE);
        s = strcpy(s, ss);
    }

    printf("%s\n", s);
}


LinkedList *split(char *s, char *separator) {
    char *token = strtok(s, separator);

    LinkedList *queue = new_LinkedList();

    while (token != NULL) {
        addLast_LinkedList(queue, token);
        token = strtok(NULL, separator);
    }

    return queue;
}

char *pop_join(LinkedList *queue, char *separator) {
    char *res = (char *) calloc(MAX_SIZE, sizeof(char));
    strcat(res, removeFirst_LinkedList(queue));

    while (queue->size > 0) {
        strcat(res, separator);
        strcat(res, removeFirst_LinkedList(queue));
    }

    return res;
}

char *decode(char *s) {
    LinkedList *queue = split(s, "#");

    LinkedList *res = new_LinkedList();

    while (queue->size > 0) {
        if (queue->size < 4) {
            return "DECODE_ERROR";
        }

        char *pos = removeFirst_LinkedList(queue);
        char *type = removeFirst_LinkedList(queue);
        int len = atoi(removeFirst_LinkedList(queue));

        char *remain = pop_join(queue, "#");

        char data[MAX_SIZE] = {'\0'};
        strncpy(data, remain, len);

        if (strlen(remain) > len) {
            queue = split((remain + len), "#");
        }

        if (strcmp(type, "2") == 0) {
            strcpy(data, decode(data));
        }

        int flag = TRUE;

        if (strcmp(type, "0") == 0) {
            strcpy(type, "Integer");
            flag = isInteger(data);
        } else if (strcmp(type, "1") == 0) {
            strcpy(type, "String");
            flag = isValidStr(data);
        } else if (strcmp(type, "2") == 0) {
            strcpy(type, "Compose");
        } else {
            flag = FALSE;
            continue;
        }

        if (flag) {
            flag = isInteger(pos);
        }

        if (flag) {
            char ele[MAX_SIZE] = {'\0'};
            strcat(ele, "[");
            strcat(ele, pos);
            strcat(ele, ",");
            strcat(ele, type);
            strcat(ele, ",");
            strcat(ele, data);
            strcat(ele, "]");

            addLast_LinkedList(res, ele);
        }
    }

    return pop_join(res, ",");
}

int main() {
    int command;
    scanf("%d", &command);
    getchar();

    char s[MAX_SIZE] = {'\0'};
    gets(s);

    if (command == 1) {
        encode(s);
    } else if (command == 2) {
        printf("%s", decode(s));
    }

    return 0;
}

C++算法源码
#include<bits/stdc++.h>

using namespace std;

map<string, string> type2num;
map<string, string> num2type;

regex num_RegExp("^\\d+$");
regex str_RegExp("^[0-9a-zA-Z\\s]+$");

bool check_encode_str(string &s) {
    stack<char> stk;

    for (const auto &c: s) {
        if (c == ']') {
            while (!stk.empty() && stk.top() != '[') {
                stk.pop();
            }

            if (stk.empty()) {
                return false;
            } else {
                stk.pop();
            }
        } else {
            stk.push(c);
        }
    }

    return stk.empty();
}

bool check_encoded(string &pos, string &type, string &data) {
    if (!regex_match(pos, num_RegExp)) {
        return false;
    }

    if (type2num.count(type) == 0) {
        return false;
    }

    if ("Integer" == type) {
        return regex_match(data, num_RegExp);
    } else if ("String" == type) {
        return regex_match(data, str_RegExp);
    }

    return true;
}

string encode(string &s) {
    size_t start = s.find("],[");
    while (start != string::npos) {
        s.replace(start, 3, "][");
        start = s.find("],[");
    }

    if (!check_encode_str(s)) {
        return "ENCODE_ERROR";
    }

 
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '[') {
            s[i] = '<';
        } else if (s[i] == ']') {
            s[i] = '>';
        }
    }

    regex p("<([^<>]+)>");

    smatch m;
    while (regex_search(s, m, p)) {
        stringstream ss(m.str(1));

        string pos;
        getline(ss, pos, ',');

        string type;
        getline(ss, type, ',');

        string data;
        getline(ss, data, ',');

        string res;

        if (check_encoded(pos, type, data)) {
            res += pos + "#";
            res += type2num[type] + "#";
            res += to_string(data.length()) + "#";
            res += data;
        }

        s = s.replace(s.find(m.str(0)), m.str(0).length(), res); 
    }

    return s;
}

deque<string> split(const string &s, char separator) {
    stringstream ss(s);
    string token;

    deque<string> queue;
    while (getline(ss, token, separator)) {
        queue.push_back(token);
    }

    return queue;
}

string pop_join(deque<string> &queue, char separator) {
    string res = queue.front();
    queue.pop_front();

    while (!queue.empty()) {
        res += separator;
        res += queue.front();
        queue.pop_front();
    }

    return res;
}

bool check_decoded(string &pos, string &type, string &data) {
    if (!regex_match(pos, num_RegExp)) {
        return false;
    }

    if (num2type.count(type) == 0) {
        return false;
    }

    if ("0" == type) {
        return regex_match(data, num_RegExp);
    } else if ("1" == type) {
        return regex_match(data, str_RegExp);
    }

    return true;
}

string decode(const string &str) noexcept(false) {
    deque<string> queue = split(str, '#');

    deque<string> res;

    while (!queue.empty()) {
        if (queue.size() < 4) {
            return "DECODE_ERROR";
        }

        string pos = queue.front();
        queue.pop_front();

        string type = queue.front();
        queue.pop_front();

        int len = stoi(queue.front());
        queue.pop_front();

        string remain = pop_join(queue, '#');

        string data = remain.substr(0, len);

        if (remain.length() > len) {
            queue = split(remain.substr(len), '#');
        }

        if ("2" == type) {
            data = decode(data);
        }

        if (check_decoded(pos, type, data)) {
         
            res.emplace_back("[" + pos + "," + num2type[type] + "," + data + "]");
        }

    }

    return pop_join(res, ',');

}

int main() {
    string command;
    getline(cin, command);

    string str;
    getline(cin, str);

    type2num["Integer"] = "0";
    type2num["String"] = "1";
    type2num["Compose"] = "2";

    num2type["0"] = "Integer";
    num2type["1"] = "String";
    num2type["2"] = "Compose";

    if (command == "1") {
        cout << encode(str) << endl;
    } else if (command == "2") {
        cout << decode(str) << endl;
    }

    return 0;
}