(C卷,100分)- 数据单元的变化替换（Java & JS & Python & C）

题目描述

将一个 csv 格式的数据文件中包含有单元格引用的内容替换为对应单元格内容的实际值。

comma separated values(CSV) 逗号分隔值，csv 格式的数据文件使用逗号 "," 作为分隔符将各单元的内容进行分隔。

输入描述

1. 输入只有一行数据，用逗号分隔每个单元格，行尾没有逗号。最多26个单元格，对应编号A~Z。
    
2. 每个单元格的内容包含字母和数字，以及使用 '<>' 分隔的单元格引用，例如：<A>表示引用第一个单元的值。
    
3. 每个单元格的内容，在替换前和替换后均不超过100个字符。
    
4. 引用单元格的位置不受限制，允许排在后面的单元格被排在前面的单元格引用。
    
5. 不存在循环引用的情况，比如下面这种场景是不存在的：

   A单元恪：aCd<B>8U

   B单元格：KAy<A>uZq0
    

6. 不存在多重 '<>' 的情况，一个单元只能引用一个其他单元格。比如下面这种场景是不存在的：

   A单元格：aCdOu

   B单元格：kAydzco

   C单元格：y<<A><B>>d

输出描述

输出替换后的结果

用例

题目解析

本题应该主要是考察递归。

因为单元格内含有"引用1"，我们需要根据"引用1"，去找引用的单元格1内容，而被引用的单元格1中也可能存在"引用2"，我们需要根据"引用2"，去找引用的单元格2内容，….，因此需要不停地根据"引用"找下去，直到某个引用的单元格内容中不存在"引用"，然后开始回溯。

这个逻辑很容易想到用递归去完成。而且本题已经说明了：

• 不存在循环引用的情况
• 不存在多重 '<>' 的情况（嵌套引用）

因此，递归的逻辑非常简单。

本题用例3给出了一个异常情况：

• <A>

即发生了自引用，我理解其实也算是循环引用。对于异常情况，要输出-1。

本题的主要难点应该在于异常情况的发掘。我觉得，还可能会存在如下异常用例：

• A,B,12<AB>3,D,E,F
• A,B,12<1>3,D,E,F
• A,B,12<Z>3,D,E,F

即

• <>中可能有多个字母（也可能是多个字母，数字）
• <>中的字符不是字母
• <>中的单个字母超出给出的单元格长度范围

这些都算是异常情况。

即我们应该对<>中的内容做如下判断：

• 内容长度只能是1
• 内容只能是A~Z字母
• 内容的单个字母对应的索引，不能超出输入单元格数量

JS算法源码

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

// 输入处理
void (async function () {
  const cells = (await readline()).split(",");

  const regexp = /(<.*?>)/;

  function changeCell(index) {
    // 通过正则匹配出单元格内容中"引用字符串"
    let matchers = regexp.exec(cells[index]);

    while (matchers != undefined) {
      // reference记录引用字符串
      const reference = matchers[0];

      // 引用单元格编号只能是A~Z的字母，即引用引用字符串长度只能是3，比如"<A>"
      if (reference.length != 3) {
        return false;
      }

      // 引用单元格的编号
      const reference_cellNum = reference[1];
      // 当前单元格的编号
      const self_cellNum = String.fromCharCode(65 + index);

      // 引用单元格编号只能是A~Z的字母，且不能自引用
      if (
        reference_cellNum < "A" ||
        reference_cellNum > "Z" ||
        reference_cellNum == self_cellNum
      ) {
        return false;
      }

      // 引用单元格的数组索引， 'A' -> 0  ... 'Z' -> 25
      const reference_index = reference_cellNum.charCodeAt() - 65;

      // 引用单元格编号不存在
      if (reference_index >= cells.length) {
        return false;
      }

      if (!changeCell(reference_index)) return false;

      // 将单元格内容中的引用部分，替换为被引用的单元格的内容
      cells[index] = cells[index].replace(reference, cells[reference_index]);

      matchers = regexp.exec(cells[index]);
    }

    return true;
  }

  for (let i = 0; i < cells.length; i++) {
    // 替换单元格中的引用，替换失败，则返回-1
    if (!changeCell(i)) {
      return console.log("-1");
    }
  }

  // 替换成功，则记录单元格内容
  console.log(cells.join(","));
})();

Java算法源码

import java.util.Scanner;
import java.util.StringJoiner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {
  static String[] cells;
  static Pattern p = Pattern.compile("(<.*?>)");

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    cells = sc.nextLine().split(",");
    System.out.println(getResult());
  }

  public static String getResult() {
    StringJoiner sj = new StringJoiner(",");

    for (int i = 0; i < cells.length; i++) {
      // 替换单元格中的引用，替换失败，则返回-1
      if (!changeCell(i)) return "-1";
      // 替换成功，则记录单元格内容
      sj.add(cells[i]);
    }

    return sj.toString();
  }

  public static boolean changeCell(int index) {
    // 通过正则匹配出单元格内容中"引用字符串"
    Matcher m = p.matcher(cells[index]);

    while (m.find()) {
      // reference记录引用字符串
      String reference = m.group(0);

      // 引用单元格编号只能是A~Z的字母，即引用引用字符串长度只能是3，比如"<A>"
      if (reference.length() != 3) {
        return false;
      }

      // 引用单元格的编号
      char reference_cellNum = reference.charAt(1);
      // 当前单元格的编号
      char self_cellNum = (char) ('A' + index);

      // 引用单元格编号只能是A~Z的字母，且不能自引用
      if (reference_cellNum < 'A' || reference_cellNum > 'Z' || reference_cellNum == self_cellNum) {
        return false;
      }

      // 引用单元格的数组索引， 'A' -> 0  ... 'Z' -> 25
      int reference_index = reference_cellNum - 'A';

      // 引用单元格编号不存在
      if (reference_index >= cells.length) {
        return false;
      }

      if (!changeCell(reference_index)) return false;

      // 将单元格内容中的引用部分，替换为被引用的单元格的内容
      cells[index] = cells[index].replaceAll(reference, cells[reference_index]);
      // 重新正则匹配
      m = p.matcher(cells[index]);
    }

    return true;
  }
}

Python算法源码

import re
regexp = re.compile(r"(<.*?>)")

# 输入获取
cells = input().split(",")


def changeCell(index):
    # 通过正则匹配出单元格内容中"引用字符串"
    matchers = regexp.findall(cells[index])

    # reference记录引用字符串
    for reference in matchers:
        # 引用单元格编号只能是A~Z的字母，即引用引用字符串长度只能是3，比如"<A>"
        if len(reference) != 3:
            return False

        # 引用单元格的编号
        reference_cellNum = reference[1]
        # 当前单元格的编号
        self_cellNum = chr(65 + index)

        # 引用单元格编号只能是A~Z的字母，且不能自引用
        if reference_cellNum < 'A' or reference_cellNum > 'Z' or reference_cellNum == self_cellNum:
            return False

        # 引用单元格的数组索引， 'A' -> 0  ... 'Z' -> 25
        reference_index = ord(reference_cellNum) - 65

        # 引用单元格编号不存在
        if reference_index >= len(cells):
            return False

        if not changeCell(reference_index):
            return False

        # 将单元格内容中的引用部分，替换为被引用的单元格的内容
        cells[index] = cells[index].replace(reference, cells[reference_index])

    return True


# 算法入口
def getResult():
    for i in range(len(cells)):
        # 替换单元格中的引用，替换失败，则返回-1
        if not changeCell(i):
            return "-1"

    # 替换成功，则记录单元格内容
    return ",".join(cells)


# 算法调用
print(getResult())

C算法源码

#include <stdio.h>
#include <string.h>

#define TRUE 1
#define FALSE 0

#define MAX_SIZE 26
#define MAX_CELL_CONTENT_LENGTH 110

// cells[i]记录每个单元格的内容
char cells[MAX_SIZE][MAX_CELL_CONTENT_LENGTH];
int cells_size = 0;

// res记录最后打印结果
char res[MAX_SIZE * MAX_CELL_CONTENT_LENGTH] = {''};

int changeCell(int index) {
    // 原始单元格内容
    char *cell = cells[index];
    unsigned long long cell_length = strlen(cell);

    // 替换引用后的单元格内容
    char cell_changed[MAX_CELL_CONTENT_LENGTH] = {''};
    unsigned long long cell_changed_length = 0;

    int l = 0;
    while (cell[l] != '') {
        if (cell[l] != '<') {
            // 非<>中的内容直接记录到cell_changed
            cell_changed[cell_changed_length++] = cell[l++];
            continue;
        }

        // 引用单元格编号只能是A~Z的字母，即引用引用字符串长度只能是3，比如"<A>"
        // 因此 l ~ l+2 是引用范围，l指向'<'， l+2指向'>'， l+1指向单元格编号
        if (cell[l + 2] != '>') {
            return FALSE;
        }

        // 引用单元格的编号
        char reference_cell_num = cell[l + 1];
        // 当前单元格的编号
        char self_cell_num = (char) ('A' + index);

        // 引用单元格编号只能是A~Z的字母，且不能自引用
        if (reference_cell_num < 'A' || reference_cell_num > 'Z' || reference_cell_num == self_cell_num) {
            return FALSE;
        }

        // 引用单元格的数组索引， 'A' -> 0  ... 'Z' -> 25
        int reference_index = reference_cell_num - 'A';

        // 引用单元格编号不存在
        if (reference_index >= cells_size) {
            return FALSE;
        }

        if (!changeCell(reference_index)) return FALSE;

        // 将单元格内容中的引用部分，替换为被引用的单元格的内容
        strcat(cell_changed, cells[reference_index]);
        // 将 “引用” 替换为 “单元格内容”后，更新cell_changed的长度
        cell_changed_length = strlen(cell_changed);

        // 将 l 移动到 l+2指向的'>' 后面
        l += 3;
    }

    strcpy(cells[index], cell_changed);

    return TRUE;
}

int main() {
    char s[MAX_SIZE * MAX_CELL_CONTENT_LENGTH];
    scanf("%s", s);

    // 按照分隔符","截取输入字符串
    char *token = strtok(s, ",");
    while (token != NULL) {
        strcpy(cells[cells_size++], token);
        token = strtok(NULL, ",");
    }

    // 对每个单元格内容进行“引用”替换
    for (int i = 0; i < cells_size; i++) {
        if (!changeCell(i)) {
            // 如果某个单元格"引用"替换失败，则返回"-1"
            puts("-1");
            return 0;
        } else {
            // 否则记录该单元格内容到结果字符串
            strcat(res, cells[i]);

            if (i != cells_size - 1) {
                strcat(res, ",");
            }
        }
    }

    puts(res);

    return 0;
}