rule_解析`````````````````
"""编写一个Python函数，该函数接受两个参数：
一个文本文件【rule】和一个字符串【input】，
请根据文件中【rule】的替换规则返回一个字符串【output】。
def apply_replacement_rules(rules, input_string):
# 你的代码【rule】
解析要求：
1、文本文件【rule】包含按顺序应用的替换规则。
2、每条规则是由空格分隔的两个字符串：s1 s2，其中s1和s2是不包含任何空格字符的字符串。
其含义是：对于输入字符串中的每个子字符串s1，
如果该子字符串没有被之前的任何规则更改过，
则将其替换为s2。
举例：
考虑文件rule.txt的内容如下（包含3条规则）：
abc cde
ab b
c a
它在输入字符串babcabdcdc上的工作过程如下：
1.第一条规则：b + cde + abdcdc #abc cde
2.第二条规则：b + cde + b + dcdc #ab b
3.第三条规则：b + cde + b + d + a + d + a #c a
（注意，尽管“cde”包含“c”，但它不会被第三条规则出发，因为它是第一条规则产生的新字符串，而不是来自原始字符串）
所以输出是 bcdebdada
请注意：参数规则【rule】不是固定的， 你的程序应该适用于任何顺序与任何替换规则，
如：c ab
abc cde
ab b
或
abcd ab
cde bcd
ade bc
请你尝试使用最优的时间复杂度来解决这个问题
解题思路：
一、先按行读取rule.txt文件，因其格式固定为每行一条规则，且每行格式为s1 s2，
读取时将其存为字典，该字典rule_dict格式为{n：[s1,s2]},n为行数
二、构造状态字典，用于存储字符串修改的历史状态及当前状态，该状态字典随规则顺序流动而更新。
如：输入字符串babcabdcdc：
1.第一条规则：b + cde + abdcdc #abc cde
此时该字典str_status为：
{1:{"source_str":"babcabdcdc","new_str":"bcdeabdcdc","change_index":["1,3"]}}
字段说明：键1表示第一条规则，键1对应的值表示第一条规则运行后的状态，source_str表示
执行第一条规则之前的输入字符串，new_str表示执行第一条规则之后的输出字符串，change_index"表示
new_str中哪一段索引是被改变的索引
2.第二条规则：b + cde + b + dcdc #ab b
此时该字典str_status为：
{1:{"source_str":"babcabdcdc","new_str":"bcdeabdcdc","change_index":["1,3"]},
2:{"source_str":"bcdeabdcdc","new_str":"bcdebdcdc","change_index":["1,3","4"]},
}
3.第三条规则：b + cde + b + d + a + d + a #c a
此时该字典str_status为：
{1:{"source_str":"babcabdcdc","new_str":"bcdeabdcdc","change_index":["1,2,3"]},
2:{"source_str":"bcdeabdcdc","new_str":"bcdebdcdc","change_index":["1,2,3","4"]},
3:{"source_str":"bcdebdcdc","new_str":"bcdebdada","change_index":["1,2,3","4","6,8"]},
}
三、字符串按规则处理函数
传入rule_dict和原生字符串。按照规则进行处理：对于输入字符串中的每个子字符串s1，
如果该子字符串没有被之前的任何规则更改过（通过str_status判断有没有更改过），则将其替换为s2，
之后更新str_status"""
"""编写一个Python函数，该函数接受两个参数：
一个文本文件【rule】和一个字符串【input】，
请根据文件中【rule】的替换规则返回一个字符串【output】。
def apply_replacement_rules(rules, input_string):
# 你的代码【rule】
解析要求：
1、文本文件【rule】包含按顺序应用的替换规则。
2、每条规则是由空格分隔的两个字符串：s1 s2，其中s1和s2是不包含任何空格字符的字符串。
其含义是：对于输入字符串中的每个子字符串s1，
如果该子字符串没有被之前的任何规则更改过，
则将其替换为s2。
举例：
考虑文件rule.txt的内容如下（包含3条规则）：
abc cde
ab b
c a
它在输入字符串babcabdcdc上的工作过程如下：
1.第一条规则：b + cde + abdcdc #abc cde
2.第二条规则：b + cde + b + dcdc #ab b
3.第三条规则：b + cde + b + d + a + d + a #c a
（注意，尽管“cde”包含“c”，但它不会被第三条规则出发，因为它是第一条规则产生的新字符串，而不是来自原始字符串）
所以输出是 bcdebdada
请注意：参数规则【rule】不是固定的， 你的程序应该适用于任何顺序与任何替换规则，
如：c ab
abc cde
ab b
或
abcd ab
cde bcd
ade bc
请你尝试使用最优的时间复杂度来解决这个问题
解题思路：
一、先按行读取rule.txt文件，因其格式固定为每行一条规则，且每行格式为s1 s2，
读取时将其存为字典，该字典rule_dict格式为{n：[s1,s2]},n为行数
二、构造状态字典，用于存储字符串修改的历史状态及当前状态，该状态字典随规则顺序流动而更新。
如：输入字符串babcabdcdc：
1.第一条规则：b + cde + abdcdc #abc cde
此时该字典str_status为：
{1:{"source_str":"babcabdcdc","new_str":"bcdeabdcdc","change_index":["1,3"]}}
字段说明：键1表示第一条规则，键1对应的值表示第一条规则运行后的状态，source_str表示
执行第一条规则之前的输入字符串，new_str表示执行第一条规则之后的输出字符串，change_index"表示
new_str中哪一段索引是被改变的索引
2.第二条规则：b + cde + b + dcdc #ab b
此时该字典str_status为：
{1:{"source_str":"babcabdcdc","new_str":"bcdeabdcdc","change_index":["1,3"]},
2:{"source_str":"bcdeabdcdc","new_str":"bcdebdcdc","change_index":["1,3","4"]},
}
3.第三条规则：b + cde + b + d + a + d + a #c a
此时该字典str_status为：
{1:{"source_str":"babcabdcdc","new_str":"bcdeabdcdc","change_index":["1,2,3"]},
2:{"source_str":"bcdeabdcdc","new_str":"bcdebdcdc","change_index":["1,2,3","4"]},
3:{"source_str":"bcdebdcdc","new_str":"bcdebdada","change_index":["1,2,3","4","6,8"]},
}
三、字符串按规则处理函数
传入rule_dict和原生字符串。按照规则进行处理：对于输入字符串中的每个子字符串s1，
如果该子字符串没有被之前的任何规则更改过（通过str_status判断有没有更改过），则将其替换为s2，
之后更新str_status"""
import re
def read_rules_file(file_path):
rule_dict = {}
if "\n" in file_path:
for n, line in enumerate(file_path.split("\n")):
s1, s2 = line.strip().split()
rule_dict[n] = [s1, s2]
else:
with open(file_path, 'r', encoding='utf-8') as file:
for n, line in enumerate(file, start=1):
s1, s2 = line.strip().split()
rule_dict[n] = [s1, s2]
return rule_dict
def find_substring(main_string, sub_string):
indexes = [m.start() for m in re.finditer('(?={})'.format(re.escape(sub_string)), main_string)]
target_index = []
for index in indexes:
if main_string.find(sub_string) == -1:
return False
else:
target = list(range(index, index + len(sub_string)))
str_target = ",".join(map(str, target))
target_index.append(str_target)
return target_index
def replace_by_indices(input_str, indices_list, replacement):
new_str = list(input_str)
for i, indices in enumerate(indices_list):
#获取起始位置和结束位置
start, end = map(int, [indices.split(',')[0], indices.split(',')[-1]])
#考虑切片长度与要替换的字符串长度不等的情况
len_qie = len(replacement) - (end + 1 - start)
start = start + len_qie * i
end = end + len_qie * i
new_str[start:end + 1] = replacement
return ''.join(new_str)
def parse_number_string(s: str):
"""将连续数字字符串转换为整数列表"""
return [int(n) for n in s.split(',')]
def check_relationship(s1: str, s2: str):
"""
判断两个连续数字字符串是否存在交叉或包含关系。
:param s1: 第一个连续数字字符串
:param s2: 第二个连续数字字符串
:return: 返回关系类型，'none', 'cross', 或 'contain'
"""
# 将字符串转换为整数列表
list1 = parse_number_string(s1)
list2 = parse_number_string(s2)
# 获取每个列表的边界值
min1, max1 = min(list1), max(list1)
min2, max2 = min(list2), max(list2)
# 检查包含关系
if min1 >= min2 and max1 <= max2:
return True
elif min2 >= min1 and max2 <= max1:
return True
# 检查交叉关系
if max1 >= min2 and min1 <= max2:
return True
elif max2 >= min1 and min2 <= max1:
return True
# 如果既不交叉也不包含，返回 'none'
return False
def apply_replacement_rules(rules_file, input_string: str):
rule_dict = read_rules_file(rules_file)
# 规则条数
len_rule_dict = len(rule_dict)
str_status = {}
current_str = input_string
for rule_num, (s1, s2) in rule_dict.items():
if not str_status: # 如果为空，则为第一次规则
# 记录第一条规则执行前的s1的所有位置
before_pro = find_substring(input_string, s1)
if before_pro: # 只有s1存在于input_string中时才考虑替换
current_str = input_string.replace(s1, s2)
if len(s1) == len(s2): # 当s1等于s2的长度时直接替换并更新状态字典
str_status[rule_num] = {
"source_str": input_string,
"new_str": current_str,
"change_index": before_pro
}
else: # 如果不等
len_d = len(s2) - len(s1)
before_pro_new = []
for index_ren, index_replace in enumerate(before_pro):
list_index = index_replace.split(",")
if len_d < 0: # 如果小于
for i in range(abs(len_d)):
list_index.pop(-1)
else: # 如果大于
N_ = 0
for i in range(abs(len_d)):
N_ += 1
list_index.append(str(int(list_index[-1]) + N_ + abs(len_d) * index_ren))
list_index[0] = str(int(list_index[0]) + abs(len_d) * index_ren)
list_index = ",".join(list_index)
before_pro_new.append(list_index)
str_status[rule_num] = {
"source_str": input_string,
"new_str": current_str,
"change_index": before_pro_new
}
else:
# 上次执行规则后的字符串
new_str = str_status[sorted(list(str_status.keys()))[-1]]["new_str"]
# 准备改动的位置
before_pro = find_substring(new_str, s1)
# 准备改动的位置，缓存
before_pro_temp = find_substring(new_str, s1)
# 已经改动的位置
change_index = str_status[sorted(list(str_status.keys()))[-1]]["change_index"]
# 只有s1存在于input_string中时才考虑替换
if before_pro:
# 每一个准备改动的位置
for pre_chage in before_pro_temp:
# 每一个已经改动的位置
for change_part in change_index:
# 如果准备改动的位置与已经改动的位置存在交叉、包含关系
if check_relationship(pre_chage, change_part):
# 将不可改动的位置从准备改动的位置移除
before_pro.pop(before_pro.index(pre_chage))
# 将可以改动的位置按索引进行替换
current_str = replace_by_indices(new_str, before_pro, s2)
# 状态更新
before_pro_new = change_index + before_pro
str_status[rule_num] = {
"source_str": new_str,
"new_str": current_str,
"change_index": before_pro_new
}
return current_str, str_status
# Example usage
'''常规情况'''
# rules_file = "rule.txt"
# rules_file = "abc cde\nab b\nc a"#bcdebdada
# rules_file = "c ab\nabc cde\nab b" # bbabbdabdab
# input_string = "babcabdcdc"
# output_string, status = apply_replacement_rules(rules_file, input_string)
# print("Output String:", output_string)
# print("Status:", status)
'''特殊情况'''
# rules_file = "abcd ab\ncde bcd\nade bc"#babcabdcdc
# input_string = "babcabdcdc"
# output_string, status = apply_replacement_rules(rules_file, input_string)
# print("Output String:", output_string)
# print("Status:", status)
'''自测试'''
# rules_file = "ab aby\ncde bcid\nade bc\nb g" # gabycdabydbcidc
# input_string = "babcdabdcdec"
# output_string, status = apply_replacement_rules(rules_file, input_string)
# print("Output String:", output_string)
# print("Status:", status)
'''问题数据'''
# rules_file = "bcd ac\ncd ba\nab dd\nc a" # ddaddaaacba
# input_string = "abcabcabcdcd"
# output_string, status = apply_replacement_rules(rules_file, input_string)
# print("Output String:", output_string)
# print("Status:", status)