（我特意去掉了有人添加的 "Python "標簽，以便讓這個問題不受語言限制。
我想我設法通過為每個括號解開一個堆疊來迭代解決這個問題，這是我滿意的解決方案（假設它能作業）。但是我沒能實作一個單一的函式遞回。誰能幫幫我？我所嘗試的結果對我來說太復雜了，因為根據逗號和大括號之間的關系，需要追加而不是擴展的不同方案。
對于這樣的事情，是否有一個優雅的遞回法？我也希望得到任何關于其他型別的既定決議/語言方法的建議，我可以為這種問題研究。
問題描述：給定一串字母、有效的大括號和逗號；擴展大括號，使其結果包括緊靠大括號左側的字母子串與大括號內的每個逗號分隔的字母子串的所有可能性。大括號可以嵌套。
例子：
"abc{d,e}f{g,hi}" => ['abcdfg', 'abcdfhi', 'abcefg', 'abcefhi']
"abc{d{0,1},e}f{g{0{a,b},1,2},hi}" =>
['abcd0fg0a', 'abcd0fg0b', 'abcd0fg1', 'abcd0fg2', 'abcd0fhi',
'abcd1fg0a', 'abcd1fg0b', 'abcd1fg1', 'abcd1fhi',
'abcefg0a', 'abcefg0b', 'abcefg1', 'abcefg2', 'abcefhi']
(希望能作業)迭代的Python代碼：
(希望能作業)
# Brace expansion。
# Example:
# input "abc{d,e}f{g,hi}"
# output ["abcdfg", "abcdfhi", "abcefg", "abcefhi"]
def f（s）。
堆疊 = []
i = 0: Stack = []
while i < len（s）。
j = i
while s[j] not in ['{'/span>, '}', ','] 。
j = 1 1
if s[i:j]:
stack.append([s[i:j]])
i = j
if s[i] == '{'/span>:
stack.append('{')
i = 1
if s[i] == ', ':
i = 1: i = 1
# Unwind stack: i = 1.
if s[i] == '}'/span>:
# Get comma, separated elements.
lst = []
while stack[-1] != '{'/span>:
lst.extend(reversed(stack.pop())
lst = reversed(lst)
stack.pop() # Remove '{'.
pfxs = reversed(stack.pop() )
stack.append([pfx sfx for pfx in pfxs for sfx in lst] )
i =1
# 堆疊的笛卡爾乘積。
結果 = []
for i in range(1, len（stack）):
result = [pfx sfx for pfx in stack[i-1] for sfxin stack[i]]
return result
輸出：
s = "abc{d,e}f{g,hi}"/span>
print(s)
print(f(s))
s = "abc{d{0,1},e}f{g{0{a,b},1,2},hi}"/span>
print("")
列印(s)
列印(f(s))
""
abc{d,e}f{g,hi}
['abcdfg', 'abcdfhi', 'abcefg', 'abcefhi']
abc{d{0,1},e}f{g{0{a,b},1,2},hi}
['abcd0fg0a', 'abcd0fg0b', 'abcd0fg1', 'abcd0fg2', 'abcd0fhi' 。
'abcd1fg0a', 'abcd1fg0b', 'abcd1fg1', 'abcd1fhi',
'abcefg0a', 'abcefg0b', 'abcefg1', 'abcefg2', 'abcefhi']
""
uj5u.com熱心網友回復：
前思后想
我讀到了 "cartesian product"，所以我的第一反應當然是匯入 itertools模塊。。第二，由于大括號的嵌套特性，我將使用遞回。
第三，有兩樣東西我們可以分割字串：逗號和大括號。因此，我將撰寫兩個相互遞回的函式：一個用于在逗號上展開，另一個用于在大括號上展開。
函式expand_commas將嘗試在逗號上分割字串。函式expand_braces將假定字串在上層不包含逗號（也就是說，它可能有隱藏在大括號內的逗號，但在大括號外沒有可見的逗號）。
第四，類str有一個方法.split，它可能方便在,和{和}上分割字串；但是In不能使用它，因為我希望分割時忽略嵌套字符。因此，我將不得不寫我自己的函式get_commas和get_braces，只檢測非嵌套的逗號和大括號。
Python代碼
import itertools
# returns a pair of indices:
# 字串中第一個'{'的索引;
# 其匹配的'}'的索引。
def get_braces（s）。
i = s.index('{')
j = i 1
深度=0
while j < len(s) and (depth > 0 or s[j] ! = '}'）。)
if s[j] == '{':
深度 = 1 '{': 深度 = 1
elif s[j] == '}'/span>:
深度 -= 1: 深度 -= 1.
j = 1: depth -= 1
return i,j
# 回傳索引串列：
#字串中每個','的索引。
# 除了隱藏在大括號中的','之外。
def get_commas（s）。
深度 = 0
逗號 = []
for i,c in enumerate（s）。
if c == '{'/span>:
深度 = 1: 深度 = 1.
elif c == '}'/span>:
深度 -= 1: 深度
elif depth == 0 and c == ', ' :
commas.append(i)
return commas
# 對逗號進行分割。
# 對子字串進行遞回呼叫。
# 回傳備選方案的串列。
def expand_commas（s）。
commas = get_commas(s)
if commas:
return list(itertools.chain. from_iterable(expand_braces(s[i 1: j]) for i,j in zip（[-1] commas, commas [len(s)]))
else:
return expand_braces(s)
# 假設大括號外沒有逗號。
# 在第一個'{'和其匹配的'}'上進行分割。
# 進行遞回呼叫，回傳笛卡爾乘積。
def expand_braces（s）。
if '{' not in s:
return [s] 。
else:
i,j = get_braces(s)
下綴 = expand_commas(s[i 1:j])
后綴 = expand_braces(s[j 1:] )
return list(''/span>. join(p) for p in itertools.product([s[:i]], infixes, suffixes)
測驗
# balanced string。
print(expand_commas("abc{d{0,1},e}f{g{0{a,b},1,2},hi}"/span>)
# ['abcd0fg0a', 'abcd0fg0b', 'abcd0fg1', 'abcd0fg2', 'abcd0fhi',/span>
# 'abcd1fg0a', 'abcd1fg0b', 'abcd1fg1', 'abcd1fg2', 'abcd1fhi',
# 'abcefg0a', 'abcefg0b', 'abcefg1', 'abcefg2', 'abcefhi']
# only commas 逗號。
print(expand_commas("a,b,c")
# ['a', 'b', 'c'].
# 不匹配的大括號：缺少閉合大括號。
print(expand_commas("abc{d{0,l},e}f{g{0{a,b")
# ['abcd0fg0a', 'abcd0fg0b', 'abcd1fg0a', 'abcd1fg0b', 'abcefg0a', 'abcefg0b']
print(expand_commas("abc{d{0,1},e}f{g{0{a,b}}"/span>)
# ['abcd0fg0a', 'abcd0fg0b', 'abcd1fg0a', 'abcd1fg0b', 'abcefg0a', 'abcefg0b']
# mismatched braces: extra closing brace
print(expand_commas("abc{d,e}}{f,g}}"/span>)
# ['abcd}f', 'abce}f', 'g}}']
# 空括號。
print(expand_commas("abc{}d"/span>)
# ['abcd']/span>
# 空逗號。
print(expand_commas("abc{,,}d")
# ['abcd', 'abcd', 'abcd', 'abcd']/span>
uj5u.com熱心網友回復：
為了區分遞回是由逗號啟動還是由大括號啟動的情況，我建議把應該作為引數的前綴傳遞給遞回呼叫將處理的東西。
我還將使用正則運算式對輸入進行標記。
下面是我的想法：
我將使用正則運算式對輸入進行標記。
import re
from itertools import product
def expand（s）。
tokens = re.finditer(r"[^{},] |.|$"/span>, s)
def recur（prefixes）。
token = next(tokens).group(0) or "}"/span>
if token == "}":
return 前綴
elif token == ", ":
return prefixes recur(["])
elif token == "{"/span>:
return recur([a b for a, b in product(prefixes, recur(["]) ])
else:
return recur([prefix token for prefix in prefixes])
return recur([""/span>])
呼叫示例：
s = "abc{d{0,1},e}f{g{0{a,b},1,2},hi}"
print(expand(s))
輸出：
['abcd0fg0a', 'abcd0fg0b', 'abcd0fg1'/span>, 'abcd0fg2', 'abcd0fhi',
'abcd1fg0a', 'abcd1fg0b'。'abcd1fg1', 'abcd1fg2', 'abcd1fhi',
'abcefg0a', 'abcefg0b', 'abcefg1'/span>, 'abcefg2'/span>, 'abcefhi'/span>]
帶有輸入驗證的版本
如果解決方案在大括號不平衡時應該引發一個可控的例外，那么就把這個函式擴展為：def expand（s）。
tokens = re.finditer(r"[^{},] |.|$"/span>, s)
def recur(prefixes, until):
token = next（tokens）.group(0)
if token == until:
return 前綴
elif token == "，"。
return prefixes recur(["], until)
elif token == "{":
return recur([a b for a, b in product(prefixes, recur(["], "}")], until)
elif token == "}"/span>:
raise ValueError("Unexpected closing brace")
elif token:
return recur([prefix token for prefix in prefixes], until)
else:
raise ValueError("missing closing brace")
return recur([""/span>], "")
uj5u.com熱心網友回復：
感謝trincot的精辟的見解，我能夠想出我想要的單一遞回函式。
Python代碼：
# Returns expanded braces and the
# ending index for the processed section.。
def f(s, prefixes=[''/span>], i=0)
if i == len(s):
return prefixes, i
j = i
while j < len(s) and s[j] not in ['{'_span>, '}', ','] 。
j = 1: [j].
new_prefixes = [pfx s[i:j] for pfx in prefixes]
if j == len（s）。
return new_prefixes, j
if s[j] == '}'/span>:
return new_prefixes, j 1.
if s[j] == '{'/span>:
后綴, next_idx = f(s, ['], j 1)
expanded = [pfx sfx for pfx in new_prefixes for sfx in suffixes ]
return f(s, expanded, next_idx)
if s[j] == ', ':
words, next_idx = f(s, [''/span>], j 1)
return new_prefixes words, next_idx
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/319311.html
標籤：
上一篇：Dart-遞回函式回傳null