An encoded string (s) is given, and the task is to decode it. The encoding pattern is that the occurrence of the string is given at the starting of the string and each string is enclosed by square brackets.
Note: The occurance of a single string is less than 1000.
Example 1:
Input: s = 1[b]
Output: b
Explaination: 'b' is present only one time.
Example 2:
Input: s = 3[b2[ca]]
Output: bcacabcacabcaca
Explaination: 2[ca] means 'ca' is repeated 
twice which is 'caca' which concatenated with 
'b' becomes 'bcaca'. This string repeated 
thrice becomes the output.
Your Task:
You do not need to read input or print anything. Your task is to complete the function decodedString() which takes s as the input parameter and returns the decoded string.
Expected Time Complexity: O(|s|)
Expected Auxiliary Space: O(|s|)
Constraints:
1 ≤ |s| ≤ 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Complete search

Starter code: #User function Template for python3



class Solution:

    def decodedString(self, s):

        # code here

Solutions:
class Solution:

	def decodedString(self, s):
		st = []
		ans = ''
		for i in range(len(s)):
			if s[i] == ']':
				x = ''
				while st[-1] != '[':
					x = st.pop() + x
				st.pop()
				k = ''
				while st != [] and st[-1].isdigit():
					k = st.pop() + k
				y = int(k) * x
				for i in y:
					st.append(i)
			else:
				st.append(s[i])
		while st != []:
			ans = st.pop() + ans
		return ans


class Solution:

	def decodedString(self, s):
		st = []
		for i in range(len(s)):
			if s[i] != ']':
				st.append(s[i])
			else:
				substr = ''
				while st and st[-1] != '[':
					substr = st.pop() + substr
				st.pop()
				count = ''
				while st and st[-1].isdigit():
					count = st.pop() + count
				st.append(int(count) * substr)
		return ''.join(st)


class Solution:

	def decodedString(self, s):
		f = []
		c = 0
		for i in range(len(s)):
			if s[i] != ']':
				f.append(s[i])
			else:
				flag = True
				st = ''
				while flag:
					j = f.pop()
					if j.isdigit() == True:
						while len(f) != 0 and f[-1].isdigit():
							j += f.pop()
						st *= int(j[-1::-1])
						flag = False
					elif j != '[':
						st += j
				f.append(st)
		res = ''
		for i in f:
			res += i[-1::-1]
		return res


class Solution:

	def decodedString(self, s):
		numStack = []
		strStack = []
		num = 0
		str = []
		for c in s:
			if c.isdigit():
				num = num * 10 + int(c)
			elif c == '[':
				strStack.append(str)
				numStack.append(num)
				str = []
				num = 0
			elif c == ']':
				tmp = str
				str = strStack.pop()
				count = numStack.pop()
				str.extend(tmp * count)
			else:
				str.append(c)
		return ''.join(str)


class Solution:

	def decodedString(self, s):
		stack = []
		current_str = ''
		count = 0
		for i in s:
			if i.isdigit():
				count = count * 10 + int(i)
			elif i.isalpha():
				current_str += i
			elif i == '[':
				stack.append((current_str, count))
				current_str = ''
				count = 0
			elif i == ']':
				(prev_str, prev_count) = stack.pop()
				current_str = prev_str + current_str * prev_count
		return current_str


class Solution:

	def decodedString(self, s):
		res = ''
		st = []
		for i in range(len(s)):
			if s[i] == ']':
				temp = ''
				while st and st[-1] != '[':
					temp += st[-1]
					st.pop()
				st.pop()
				temp = temp[::-1]
				subst = ''
				while st and ord(st[-1]) >= 48 and (ord(st[-1]) <= 57):
					subst += st[-1]
					st.pop()
				subst = subst[::-1]
				n = int(subst)
				for j in range(n):
					for x in temp:
						st.append(x)
			else:
				st.append(s[i])
		while st:
			res += st.pop()
		res = res[::-1]
		return res


class Solution:

	def decodedString(self, s):
		stack = []
		digit = ''
		for char in s:
			if char == ']':
				new_char = stack.pop()
				new_string = ''
				while new_char != '[':
					new_string = new_char + new_string
					new_char = stack.pop()
				multipler = int(stack.pop())
				stack.append(new_string * multipler)
			elif char.isdigit():
				digit += char
			elif char == '[':
				stack.append(digit)
				stack.append('[')
				digit = ''
			else:
				stack.append(char)
		return ''.join(stack)


class Solution:

	def decodedString(self, s):
		stack = []
		for char in s:
			if char != ']':
				stack.append(char)
			else:
				substr = ''
				while stack[-1] != '[':
					substr = stack.pop() + substr
				stack.pop()
				num = ''
				while stack and stack[-1].isdigit():
					num = stack.pop() + num
				substr *= int(num)
				stack += list(substr)
		return ''.join(stack)


class Solution:

	def decodedString(self, s):
		num_stk = []
		char_stk = []
		num_str = ''
		for i in s:
			if i.isnumeric():
				num_str += i
			else:
				if num_str:
					num_stk.append(int(num_str))
					num_str = ''
				if i == ']':
					temp_ans = ''
					while char_stk[-1] != '[':
						temp_ans = char_stk.pop(-1) + temp_ans
					char_stk.pop(-1)
					if len(char_stk) and char_stk[-1] != '[':
						char_stk[-1] += temp_ans * num_stk.pop(-1)
					else:
						char_stk.append(temp_ans * num_stk.pop(-1))
				else:
					char_stk.append(i)
		return char_stk[-1]


class Solution:

	def decodedString(self, s):
		num = ''
		nums = []
		stack = ['']
		for item in s:
			if item.isdigit():
				num += item
			elif item == '[':
				nums.append(int(num))
				num = ''
				stack.append('')
			elif item == ']':
				substring = stack.pop() * nums.pop()
				stack[-1] += substring
			else:
				stack[-1] += item
		return stack[0]


class Solution:

	def decodedString(self, s):
		string = ''
		st = []
		i = 0
		while i < len(s):
			if s[i] == ']':
				currstring = ''
				while len(st) > 0 and st[-1].isalpha():
					currstring = st.pop() + currstring
				currstring = int(st[-1]) * currstring
				st.pop()
				st.append(currstring)
			elif s[i] != '[' and s[i] != ']' and s[i].isalpha():
				st.append(s[i])
			elif s[i] != '[' and s[i] != ']' and (s[i].isalpha() == False):
				digit = ''
				while s[i].isdigit():
					digit += s[i]
					i += 1
				i -= 1
				st.append(digit)
			i += 1
		return ''.join(st)


class Solution:

	def decodedString(self, s):
		stack = []
		curstr = ''
		curnum = 0
		for it in s:
			if it == '[':
				stack.append(curstr)
				stack.append(curnum)
				curstr = ''
				curnum = 0
			elif it == ']':
				prevnum = stack.pop()
				prevstr = stack.pop()
				curstr = prevstr + prevnum * curstr
			elif it.isdigit():
				curnum = curnum * 10 + int(it)
			else:
				curstr += it
		return curstr


class Solution:

	def decodedString(self, s):
		stack = []
		i = 0
		(c, m) = (0, 1)
		while i < len(s):
			if ord('9') >= ord(s[i]) >= ord('0'):
				c = c * m + int(s[i])
				m = m * 10
			elif s[i] == '[':
				stack.append((c, i - len(str(c))))
				stack.append((s[i], i))
				(c, m) = (0, 1)
			elif s[i] == ']' and len(stack) > 0:
				(blank, stri) = stack.pop()
				(totalCount, ci) = stack.pop()
				s = s[:ci] + totalCount * s[stri + 1:i] + s[i + 1:]
				while ci < len(s):
					if ord('9') >= ord(s[ci]) >= ord('0') or s[ci] == ']':
						i = ci - 1
						break
					ci += 1
				(c, m) = (0, 1)
			i += 1
		return s


from collections import deque

class Solution:

	def decodedString(self, s):
		if '[' not in s:
			return s
		else:
			stack = deque()
			fs = ''
			num = 0
			st = ''
			flag = False
			for i in s:
				if i.isdigit() and flag == False:
					num = num * 10 + int(i)
				if i == '[':
					flag = True
					stack.append('[')
					st = st + i
				if flag == True and len(stack) != 0 and (i != '['):
					st = st + i
				if i == ']' and len(stack) != 0:
					stack.pop()
				if len(stack) == 0 and flag == True:
					temp = ''
					rss = Solution.decodedString(self, st[1:-1])
					for j in range(num):
						temp = temp + rss
					fs = fs + temp
					flag = False
					num = 0
					st = ''
				if i != '[' and i != ']' and (len(stack) == 0) and (num == 0):
					fs = fs + i
			return fs


class Solution:

	def decodedString(self, s):
		arr = []
		i = len(s) - 1
		while i >= 0:
			if s[i] == '[':
				ans = ''
				while arr[-1] != ']':
					ans += arr.pop()
				arr.pop()
				i -= 1
				num = ''
				while s[i].isdigit():
					num += s[i]
					i -= 1
				arr.append(ans * int(num[::-1]))
			else:
				arr.append(s[i])
				i -= 1
		return ''.join(arr)


class Solution:

	def decodedString(self, s):
		stk = []
		ans = ''
		i = 0
		while i < len(s):
			if s[i] == ']':
				x = ''
				while not stk[-1].isdigit():
					x += stk.pop()
				cnt = int(stk.pop())
				j = 0
				repeat = x
				while j < cnt - 1:
					x += repeat
					j += 1
				stk.append(x)
				i += 1
			elif s[i] != '[':
				if s[i].isdigit():
					d = ''
					while s[i].isdigit():
						d += s[i]
						i += 1
					stk.append(d)
				else:
					stk.append(s[i])
					i += 1
			else:
				i += 1
		while len(stk) > 0:
			ans += stk.pop()
		return ans[::-1]


class Solution:

	def decodedString(self, Str):
		st = []
		for i in range(len(s)):
			if s[i] == ']':
				temp = ''
				while len(st) > 0 and st[-1] != '[':
					temp = st[-1] + temp
					st.pop()
				st.pop()
				num = ''
				while len(st) > 0 and ord(st[-1]) >= 48 and (ord(st[-1]) <= 57):
					num = st[-1] + num
					st.pop()
				number = int(num)
				repeat = ''
				for j in range(number):
					repeat += temp
				st.extend(list(repeat))
			else:
				st.append(s[i])
		return ''.join(st)


class Solution:

	def decodedString(self, Str):
		integerstack = []
		stringstack = []
		temp = ''
		result = ''
		i = 0
		while i < len(Str):
			count = 0
			if Str[i] >= '0' and Str[i] <= '9':
				while Str[i] >= '0' and Str[i] <= '9':
					count = count * 10 + ord(Str[i]) - ord('0')
					i += 1
				i -= 1
				integerstack.append(count)
			elif Str[i] == ']':
				temp = ''
				count = 0
				if len(integerstack) != 0:
					count = integerstack[-1]
					integerstack.pop()
				while len(stringstack) != 0 and stringstack[-1] != '[':
					temp = stringstack[-1] + temp
					stringstack.pop()
				if len(stringstack) != 0 and stringstack[-1] == '[':
					stringstack.pop()
				for j in range(count):
					result = result + temp
				for j in range(len(result)):
					stringstack.append(result[j])
				result = ''
			elif Str[i] == '[':
				if Str[i - 1] >= '0' and Str[i - 1] <= '9':
					stringstack.append(Str[i])
				else:
					stringstack.append(Str[i])
					integerstack.append(1)
			else:
				stringstack.append(Str[i])
			i += 1
		while len(stringstack) != 0:
			result = stringstack[-1] + result
			stringstack.pop()
		return result


class Stack:

	def __init__(self, size):
		self.stack = [0] * size
		self.end = -1

	def isEmpty(self):
		if self.end == -1:
			return True
		else:
			return False

	def push(self, value):
		self.end += 1
		self.stack[self.end] = value

	def pop(self):
		op = self.stack[self.end]
		self.end -= 1
		return op

	def top(self):
		return self.stack[self.end]

class Solution:

	def decodedString(self, s):
		i = 0
		stack = Stack(len(s))
		stack_2 = Stack(len(s))
		temp = ''
		while i < len(s):
			if s[i].isnumeric():
				temp += s[i]
				i += 1
			elif s[i] == '[':
				stack.push(i)
				stack_2.push(temp)
				temp = ''
				i += 1
			elif s[i] == ']':
				indi = stack.pop()
				count = stack_2.pop()
				s = s[:indi - len(count)] + int(count) * s[indi + 1:i] + s[i + 1:]
				i = indi - len(count) + len(int(count) * s[indi + 1:i])
			else:
				i += 1
		return s


class Solution:

	def decodedString(self, s: str) -> str:
		stack = []
		for c in s:
			if c == ']':
				substr = ''
				while stack[-1] != '[':
					substr = stack.pop() + substr
				stack.pop()
				num = ''
				while stack and stack[-1].isdigit():
					num = stack.pop() + num
				stack.append(int(num) * substr)
			else:
				stack.append(c)
		return ''.join(stack)


class Solution:

	def decodedString(self, s):
		stack = []
		curr_count = 0
		curr_str = ''
		for c in s:
			if c.isdigit():
				curr_count = curr_count * 10 + int(c)
			elif c == '[':
				stack.append((curr_count, curr_str))
				(curr_count, curr_str) = (0, '')
			elif c == ']':
				(prev_count, prev_str) = stack.pop()
				curr_str = prev_str + curr_str * prev_count
			else:
				curr_str += c
		return curr_str


class Solution:

	def decodedString(self, s):
		(val, res, stack) = (0, '', [])
		for i in s:
			if i.isdigit():
				val = 10 * val + int(i)
			elif i == ']':
				res = stack.pop() + stack.pop() * res
			elif i == '[':
				stack.extend([val, res])
				val = 0
				res = ''
			else:
				res += i
		return res


class Solution:

	def decodedString(self, s):
		stack = []
		curNum = 0
		curStr = ''
		for i in s:
			if i == '[':
				stack.append(curStr)
				stack.append(curNum)
				curStr = ''
				curNum = 0
			elif i == ']':
				num = stack.pop()
				prevStr = stack.pop()
				curStr = prevStr + num * curStr
			elif i.isdigit():
				curNum = curNum * 10 + int(i)
			else:
				curStr += i
		return curStr


class Solution:

	def decodedString(self, s):
		stack = []
		for i in range(len(s)):
			if s[i] != ']':
				stack.append(s[i])
			else:
				sub = ''
				while stack[-1] != '[':
					sub = stack.pop() + sub
				stack.pop()
				k = ''
				while stack and stack[-1].isdigit():
					k = stack.pop() + k
				stack.append(int(k) * sub)
		return ''.join(stack)


class Solution:

	def solve(self, prefix, s, i, n, repeat):
		str = ''
		str_start = i
		while i < n:
			if s[i].isdigit():
				num = 0
				prefix_ = i
				while s[i].isdigit():
					num += int(s[i])
					num *= 10
					i += 1
				num //= 10
				(s, i) = self.solve(prefix_, s, i + 1, n, num)
				n = len(s)
			elif s[i] == ']':
				str = s[str_start:i]
				str *= repeat
				new_i = len(s[:prefix] + str)
				s = s[:prefix] + str + s[i + 1:]
				return (s, new_i)
			else:
				i += 1
		return (s, i)

	def decodedString(self, s):
		return self.solve(0, s, 0, len(s), 1)[0]


class Solution:

	def decodedString(self, s):
		i = 0
		n = len(s)
		res = ''
		while i < n:
			if s[i].isdigit():
				j = i
				while s[j].isdigit():
					j += 1
				count = int(s[i:j])
				k = j + 1
				open_count = 1
				while open_count > 0:
					if s[k] == '[':
						open_count += 1
					elif s[k] == ']':
						open_count -= 1
					k += 1
				substr = self.decodedString(s[j + 1:k - 1])
				res += count * substr
				i = k
			else:
				res += s[i]
				i += 1
		return res


class Solution:

	def decodedString(self, s):
		stack = []
		for i in list(s):
			if i != ']':
				stack.append(i)
			else:
				substr = ''
				while stack and stack[-1] != '[':
					substr = stack.pop() + substr
				stack.pop()
				times = ''
				while stack and stack[-1].isdigit():
					times = stack.pop() + times
				substr = int(times) * substr
				stack.append(substr)
		return ''.join(stack)


class Solution:

	def decodedString(self, s):
		ans = ''
		stack = list()
		s = s[::-1]
		n = len(s)
		i = 0
		while i < n:
			if s[i].isnumeric():
				if len(stack) and stack[-1] == '[':
					stack.pop()
					temp = ''
					while len(stack) and stack[-1] != ']':
						temp += stack.pop()
					stack.pop()
					val = int(s[i])
					if i + 1 < n and s[i + 1].isnumeric():
						val = int(s[i + 1] + s[i])
					temp *= int(val)
					if len(stack) and stack[-1].isalpha():
						temp += stack.pop()
					stack.append(temp)
					ans = temp
			else:
				stack.append(s[i])
			i += 1
		return ans


class Solution:

	def decodedString(self, s):
		cur_str = ''
		num = 0
		stack = []
		for i in s:
			if i.isdigit():
				num = num * 10 + int(i)
			elif i.isalpha():
				cur_str += i
			elif i == '[':
				stack.append((num, cur_str))
				cur_str = ''
				num = 0
			else:
				(digit, strr) = stack.pop()
				cur_str = strr + digit * cur_str
		return cur_str


class Solution:

	def decodedString(self, s):
		stack = []
		curstr = ''
		curnum = 0
		for c in s:
			if c.isdigit():
				curnum = curnum * 10 + int(c)
			elif c == '[':
				stack.append([curnum, curstr])
				curnum = 0
				curstr = ''
			elif c == ']':
				(pre_num, pre_str) = stack.pop()
				curstr = pre_str + curstr * pre_num
			else:
				curstr += c
		return curstr


class Solution:

	def decodedString(self, s):
		st = ['']
		num = ''
		no = []
		for i in s:
			if i.isnumeric():
				num += i
			elif i == '[':
				no.append(int(num))
				num = ''
				st.append('')
			elif i == ']':
				sub = st.pop() * no.pop()
				st[-1] += sub
			else:
				st[-1] += i
		return st[0]


class Solution:

	def decodedString(self, s):
		num = ''
		z = []
		res = ''
		stack = []
		for i in s:
			if i.isdigit():
				num += i
			elif i == '[' or i.isalpha():
				stack.append(i)
				if len(num):
					z.append(int(num))
					num = ''
			elif stack:
				s1 = ''
				while stack[-1] != '[':
					s1 = stack.pop() + s1
				stack.pop()
				stack.append(s1 * z.pop())
		for i in stack:
			res += i
		return res


class Solution:

	def decodedString(self, s):
		strings = []
		nums = []
		i = 0
		while i < len(s):
			num = ''
			if ord(s[i]) >= ord('0') and ord(s[i]) <= ord('9'):
				while ord(s[i]) >= ord('0') and ord(s[i]) <= ord('9'):
					num += s[i]
					i += 1
				num = int(num)
				nums.append(num)
			if s[i] == '[' or s[i].isalpha():
				strings.append(s[i])
			if s[i] == ']':
				number = 1
				if len(nums) != 0:
					number = nums.pop()
				substr = ''
				while strings[-1] != '[':
					substr += strings.pop()
				strings.pop()
				strings.append(substr * number)
			i += 1
		res = ''
		while len(strings) > 0:
			res += strings.pop()
		res = res[::-1]
		return res


class Solution:

	def decodedString(self, s):
		num = str()
		nums = list()
		stack = ['']
		for item in s:
			if item.isnumeric():
				num += item
			elif item == '[':
				nums.append(int(num))
				num = str()
				stack.append('')
			elif item == ']':
				substring = stack.pop() * nums.pop()
				stack[-1] += substring
			else:
				stack[-1] += item
		return stack[0]


class Solution:

	def decodedString(self, s):
		stack = []
		for item in s:
			if item != ']':
				stack.append(item)
			else:
				substring = ''
				while stack[-1] != '[':
					substring = stack.pop() + substring
				stack.pop()
				k = ''
				while stack and stack[-1].isdigit():
					k = stack.pop() + k
				k = int(k)
				stack.append(k * substring)
		return ''.join(stack)


class Solution:

	def decodedString(self, s):
		n = len(s)
		i = 0
		chstack = []
		intstack = []
		res = ''
		while i < n:
			num = 0
			if s[i].isnumeric():
				while i < n and s[i].isnumeric():
					num = num * 10 + int(s[i])
					i += 1
				intstack.append(num)
			elif s[i] == '[':
				if s[i - 1].isnumeric:
					chstack.append(s[i])
				else:
					intstack.append(1)
					chstack.append(s[i])
				i += 1
			elif s[i] == ']':
				temp = ''
				if len(intstack) != 0:
					count = intstack[-1]
					intstack.pop()
				while len(chstack) != 0 and chstack[-1] != '[':
					temp = chstack[-1] + temp
					chstack.pop()
				if len(chstack) != 0 and chstack[-1] == '[':
					chstack.pop()
				for j in range(count):
					res = temp + res
				for k in range(len(res)):
					chstack.append(res[k])
				res = ''
				i += 1
			else:
				chstack.append(s[i])
				i += 1
		while len(chstack) != 0:
			res = chstack[-1] + res
			chstack.pop()
		return res


class Solution:

	def decodedString(self, s):
		x = []
		for i in range(len(s)):
			if s[i] != ']':
				x.append(s[i])
			else:
				a = ''
				while x[-1] != '[' and len(x) > 0:
					a = x.pop() + a
				x.pop()
				k = ''
				while len(x) != 0 and x[-1].isdigit():
					k = x.pop() + k
				x.append(int(k) * a)
		return ''.join(x)


def isNum(c):
	return c >= '0' and c <= '9'

class Solution:

	def decodedString(self, s):
		ans = []
		for i in range(len(s)):
			c = s[i]
			if c == ']':
				curr = []
				while len(ans) > 0 and ans[-1] != '[':
					curr.append(ans[-1])
					ans.pop()
				ans.pop()
				curr.reverse()
				nums = ''
				while len(ans) > 0 and isNum(ans[-1]):
					nums += ans[-1]
					ans.pop()
				nums = int(nums[::-1])
				ans.extend(curr * nums)
			else:
				ans.append(c)
		return ''.join(ans)


class Solution:

	def decodedString(self, s):
		res = ''
		stack = []
		num = 0
		for c in s:
			if c == '[':
				stack.append((res, num))
				num = 0
				res = ''
			elif c == ']':
				n = stack[-1][1]
				prev = stack[-1][0]
				stack.pop()
				res = prev + res * n
			elif c.isdigit():
				num = num * 10 + int(c)
			else:
				res += c
		return res


class Solution:

	def decodedString(self, s):
		stack = []
		for i in s:
			if i != ']':
				stack.append(i)
			else:
				word = ''
				while stack and stack[-1] != '[':
					word = stack.pop() + word
				stack.pop()
				num = ''
				while stack and stack[-1].isdigit():
					num = stack.pop() + num
				stack.append(word * int(num))
		return ''.join(stack)


class Solution:

	def decodedString(self, s):
		l = list(s)
		iStack = []
		cStack = []
		st = ''
		sta = ''
		nmString = ''
		for i in l:
			if i.isnumeric():
				nmString = nmString + i
			if i.isalpha() or i == '[':
				if nmString != '':
					iStack.append(nmString)
					nmString = ''
				cStack.append(i)
			if i == ']':
				n = iStack.pop()
				while cStack[-1] != '[':
					v = cStack.pop()
					st = v + st
				cStack.pop()
				for j in range(0, int(n)):
					sta += st
				cStack.append(sta)
				st = ''
				sta = ''
		return ''.join(cStack)


class Solution:

	def decodedString(self, s):
		st = []
		for i in s:
			if i != ']':
				st.append(i)
			else:
				res = ''
				while st[-1] != '[':
					res = st.pop() + res
				st.pop()
				temp = ''
				while len(st) and len(st[-1]) == 1 and (ord(st[-1]) <= 57) and (ord(st[-1]) >= 48):
					temp = st.pop() + temp
				st.append(res * int(temp))
		return ''.join(st)


class Solution:

	def decodedString(self, s):
		a = []
		n = len(s)
		i = 0
		while i < n:
			if s[i].isalpha():
				a.append(s[i])
				i += 1
			elif s[i].isnumeric():
				x = ''
				while s[i].isnumeric():
					x += s[i]
					i += 1
				a.append(x)
			else:
				if s[i] == '[':
					a.append(s[i])
				else:
					x = ''
					while a[-1] != '[':
						x += a.pop(-1)
					a.pop(-1)
					a.append(int(a.pop(-1)) * x)
				i += 1
		x = ''
		for i in a:
			x += i
		return x[::-1]


class Solution:

	def decodedString(self, s):
		stack_1 = []
		for i in s:
			if i != ']':
				stack_1.append(i)
			else:
				temp = ''
				while len(stack_1) > 0 and stack_1[-1] != '[':
					temp = stack_1[-1] + temp
					stack_1.pop()
				stack_1.pop()
				count = 0
				power = 1
				while len(stack_1) > 0:
					num = stack_1[-1]
					try:
						num = int(stack_1[-1])
					except:
						break
					num *= power
					power *= 10
					count += num
					stack_1.pop()
				while count > 0:
					count -= 1
					for c in temp:
						stack_1.append(c)
		ans1 = ''
		while len(stack_1) > 0:
			ans1 = stack_1[-1] + ans1
			stack_1.pop()
		return ans1


class Solution:

	def decodedString(self, s):
		stack = []
		curstr = ''
		curdig = ''
		prevdig = ''
		prevstr = ''
		for i in range(len(s)):
			if s[i] == '[':
				stack.append(curstr)
				stack.append(curdig)
				curdig = ''
				curstr = ''
			elif s[i] == ']':
				prevdig = stack.pop()
				prevstr = stack.pop()
				curstr = prevstr + curstr * int(prevdig)
			elif s[i].isdigit():
				curdig += s[i]
			else:
				curstr += s[i]
		return curstr


class Solution:

	def decodedString(self, s):
		l = []
		n = len(s)
		for i in range(n):
			if s[i] == ']':
				s1 = ''
				while l[len(l) - 1] != '[':
					s1 += l[len(l) - 1]
					l.pop()
				l.pop()
				s1 = s1[::-1]
				r1 = ''
				while len(l) > 0 and l[len(l) - 1].isnumeric():
					r1 += l[len(l) - 1]
					l.pop()
				r1 = r1[::-1]
				r = int(r1)
				ans = r * s1
				for j in range(len(ans)):
					l.append(ans[j])
			else:
				l.append(s[i])
		res = ''.join(l)
		return res


class Solution:

	def decodedString(self, s):
		stack = []
		for i in s:
			if i == '[':
				stack.append(i)
			elif i == ']':
				sr = ''
				nr = ''
				while len(stack) != 0 and stack[-1] != '[':
					sr = stack.pop() + sr
				stack.pop()
				while len(stack) != 0 and stack[-1].isnumeric() == True:
					nr = stack.pop() + nr
				sr = int(nr) * sr
				stack.append(sr)
			else:
				stack.append(i)
		return ''.join(stack)


class Solution:

	def decodedString(self, s):
		stack = []
		i = 0
		result = ''
		num = ''
		while i < len(s):
			if s[i] == ']':
				if stack[-1] == '[':
					stack.pop()
					result *= int(stack.pop())
					stack.append(result)
					result = ''
					i += 1
				else:
					result = stack.pop() + result
				continue
			if s[i].isnumeric():
				num += s[i]
			else:
				stack.append(num)
				stack.append(s[i])
				num = ''
			i += 1
		return ''.join(stack)


from collections import deque

class Solution:

	def decodedString(self, s):
		stack = []
		for ch in s:
			if ch == ']':
				temp = deque()
				while stack and stack[-1] != '[':
					temp.appendleft(stack.pop())
				stack.pop()
				num = deque()
				while stack and stack[-1].isdigit():
					num.appendleft(stack.pop())
				num = int(''.join(num))
				tempStr = ''.join(temp)
				for _ in range(num):
					stack.append(tempStr)
			else:
				stack.append(ch)
		return ''.join(stack)


class Solution:

	def decodedString(self, s):
		stack = []
		curNum = 0
		curString = ''
		for c in s:
			if c == '[':
				stack.append(curString)
				stack.append(curNum)
				curString = ''
				curNum = 0
			elif c == ']':
				num = stack.pop()
				prevString = stack.pop()
				curString = prevString + num * curString
			elif c.isdigit():
				curNum = curNum * 10 + int(c)
			else:
				curString += c
		return curString


class Solution:

	def decodedString(self, s):
		st = []
		for i in range(len(s)):
			if s[i] != ']':
				st.append(s[i])
			else:
				t = ''
				while len(st) > 0 and st[-1] != '[':
					t = st.pop() + t
				st.pop()
				num = ''
				while len(st) > 0 and st[-1].isdigit():
					num = st[-1] + num
					st.pop()
				st.append(int(num) * t)
		return ''.join(st)


def rec(s):
	stack = []
	for i in range(len(s)):
		if s[i] in '0123456789' or s[i] in '[':
			stack.append(s[i])
		elif s[i] in ']':
			st = ''
			j = 0
			k = -1
			while stack[k] != '[':
				j = j + 1
				k = k - 1
			st = ''.join(stack[len(stack) - j:])
			stack = stack[0:len(stack) - j]
			stack.pop()
			r = ''
			while stack and stack[-1] in '0123456789':
				r = r + stack[-1]
				stack.pop()
			r = r[::-1]
			r = int(r)
			st = r * st
			stack.append(st)
		else:
			stack.append(s[i])
	return ''.join(stack)

class Solution:

	def decodedString(self, s):
		k = rec(s)
		return k


class Solution:

	def decodedString(self, s):
		charStack = []
		number = 0
		finalString = ''
		while s:
			st = ''
			if s[0] == '[':
				num = ''
				while charStack and charStack[-1].isdigit():
					num = charStack.pop() + num
				number = int(num)
				s = s[1:]
				(ans, s) = self.decodedString(s)
				for i in range(number):
					st += ans
				st1 = ''
				while charStack:
					st1 = charStack.pop() + st1
				finalString += st1
				finalString += st
				s = s[1:]
			elif s[0] == ']':
				st1 = ''
				while charStack:
					st1 = charStack.pop() + st1
				finalString = finalString + st1
				return [finalString, s]
			else:
				charStack.append(s[0])
				s = s[1:]
		return finalString


from collections import deque

class Solution:

	def decodedString(self, s):
		stack = deque()
		n = len(s)
		i = 0
		while i < n:
			ch = s[i]
			if ch == ']':
				st = []
				while stack[-1] != '[':
					st.append(stack.pop())
				stack.pop()
				times = int(stack.pop())
				stack.append(times * ''.join(st[::-1]))
				i += 1
			elif ch.isnumeric():
				num = ''
				while s[i] != '[':
					num += s[i]
					i += 1
				stack.append(num)
			else:
				stack.append(ch)
				i += 1
		ans = []
		while len(stack) > 0:
			ans.append(stack.popleft())
		return ''.join(ans)


class Solution:

	def decodedString(self, a):
		s = []
		res = ''
		for i in range(len(a)):
			if a[i] != ']':
				s.append(a[i])
			else:
				t = ''
				while s[-1].isalpha():
					t = s.pop() + t
				s.pop()
				n = ''
				while s and s[-1].isnumeric():
					n = s.pop() + n
				s.append(int(n) * t)
		return ''.join(s)