Python人物數學使用堆棧

-2

我在算法Meetup中收到了一個有趣的挑戰。給定一個輸入字符串，返回一個字符串，其中括號內的所有子字符串都被複制了n次，其中n是括號外的整數。括號內的字符應該簡單地連接到裏面的子字符串。例如：Python人物數學使用堆棧

2 [AB]應返回ABAB
[3 [BC]]應返回abcbcbc
2 [AB苯並[cd]]應返回abcdabcd

我已經明星ted使用堆棧實現解決方案，但是我已經感覺到，我檢查每個拆分字符的方法是關閉的，任何人有任何建議？代碼低於

class Stack: 
    def __init__(self): 
     self.items = [] 

    def push(self, item): 
     self.items.append(item) 

    def pop(self): 
     return self.items.pop() 

    def length(self): 
     return len(self.items) 

def is_number(s): 
    try: 
     int(s) 
     return True 
    except ValueError: 
     return False 

def character_math(charstr): 
    final_output = "" 
    substring = "" 
    for i in charstr: 
     myStack.push(i) 

    for m in range(myStack.length() - 2): 
     destacked = myStack.pop() 
     # We want to go to the inner-most right bracket 
     if destacked != "]": 
      substring += destacked 
     if destacked == "[": 
      possible_multiplier = myStack.pop() 
      if is_number(possible_multiplier): 
       final_output += int(possible_multiplier) * substring 
      else: 
       final_output += possible_multiplier[::-1] 
       break 
     final_output += substring[::-1] 
    return "Final output is ", final_output 

myStack = Stack() 
# 3[ab[cd]] should return 'abcdabcd' 
sample_str = '2[ab[cd]]' 
print(character_math(sample_str))

來源

2017-08-30 jmdeamer

這是真的，也許我可以更具體一些。我正在努力確定評估一系列字符的正確模式，因爲我現在的方法對於處理不同的輸入字符串來說太麻煩了。感謝Mathieu通過指向遞歸來做到這一點。 – jmdeamer

要做到這一點的最好方法是使用遞歸算法。這個想法是重複一個函數，直到條件匹配。以下是我使用的代碼，它適用於您的示例，我不認爲我忘記了其中一種可能性。

# -*-coding:Utf-8 -* 

Input = "2[ab[cd]]" 

def Treatment(STR): 

    # Exit the treatment. That's the end condition. 
    if "[" not in STR: 
     return STR 

    # Find the inner [], in this case, the "cd" part 
    Bound1_ID = len(STR) - STR[::-1].index("[") - 1 
    Bound2_ID = STR.index("]") 

    # Separate STR into : First_part + middle between [] + Last_part 
    Last_part = STR[Bound2_ID + 1:] 

    # First_part depends if there is a number or not 
    try: 
     Multiplier = int(STR[Bound1_ID - 1]) 
     First_part = STR[:Bound1_ID - 1] 
    except: 
     Multiplier = 1 
     First_part = STR[:Bound1_ID] 

    Middle_part = STR[Bound1_ID + 1: Bound2_ID] * Multiplier 

    # Assemble the new STR : 
    New_STR = First_part + Middle_part + Last_part 

    # Recursive command, repeat the function on the new STR 
    return Treatment(New_STR) 

print (Treatment(Input))

編輯：這就是它的作用：

第一次迭代：「2 AB [CD]」
第二次迭代：「2 [ABCD]」
第三次迭代： abcdabcd =>沒有更多的「[」所以停在這裏。

來源

2017-08-30 11:42:19 Mathieu

Python人物數學使用堆棧

回答

相關問題