python-programs/decodeString.py at master · kumaya/python-programs · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# given encoded input string, return decoded form
# Inp = 2[ab10[b]d]
# Out = "abbbbbbbbbbbdabbbbbbbbbbbd"

defdecodeStr(inp):
counts= []
i=0
whilei<len(inp):
ifinp[i].isdigit():
count=0
whileinp[i] !="[":
count=count*10+int(inp[i])
i+=1
ifcount>0:
counts.append(count)
else:
i+=1
strStack= []
foriininp:
ifi=="]":
tmp= []
whilestrStack[-1] !="[":
x=strStack.pop()
tmp.append(x)
strStack.pop() # remove [
count=counts.pop()
# count = int(strStack.pop())
tmp=tmp*int(count)
strStack.append("".join(tmp[::-1]))
elifnoti.isdigit():
strStack.append(str(i))
returnstrStack[0]


if__name__=='__main__':
inp="2[ab2[bc]d]"
res=decodeStr(inp)
printres
assertres=="abbcbcdabbcbcd"
inp="2[a13[b]]"
res=decodeStr(inp)
printres
assertres=="abbbbbbbbbbbbbabbbbbbbbbbbbb"
inp="2[a10[b]]"
res=decodeStr(inp)
printres
assertres=="abbbbbbbbbbabbbbbbbbbb"