#!/usr/bin/python

import os
import sys

def rp_parse(string):

	# Stage 1: create expression
	string = string.replace('(', '+(').replace(')', ')+')
	while string != string.replace('(+(', '((').replace(')+)', '))').replace('++', '+'):
		string = string.replace('(+(', '((').replace(')+)', '))').replace('++', '+')
	if string[0] == '+':
		string = string[1:]
	if string[len(string)-1] == '+':
		string = string[:len(string)-1]

	# Stage 2: reverse_polish_notation(string)
	#	Priority: 1: '()' ; 2: '+'
	#	Alias: '()' => '<<'
	op_stack  = list()
	out_stack = list()
	counter   = 0
	out_stack.append('')
	for c in string:
		if c == '(':
			op_stack.append('(')
			if out_stack[counter]:
				out_stack.append('')
				counter += 1
		elif c == ')':
			i = len(op_stack) - 1
			while op_stack[i] != '(' and i >= 0:
				out_stack.append(op_stack[i])
				op_stack.pop()
				counter += 1
				i -= 1
			op_stack.pop()	# take '(' out
			if out_stack[counter] == '':
				out_stack[counter] = "<<"
				out_stack.append('')
				counter += 1
			else:
				out_stack.append('<<')
				out_stack.append('')
				counter += 2
		elif c == '+':
			op_stack.append('+')
			if out_stack[counter]:
				out_stack.append('')
				counter += 1
		else:
			out_stack[counter] += c
	
	if out_stack[counter] == '':
		del out_stack[counter]

	i = len(op_stack) - 1
	while i >= 0:
		out_stack.append(op_stack[i])
		i -= 1

	return out_stack


def rp_reverse(string):
	i = len(string) - 1
	buff = str()
	while i >= 0:
		buff += string[i]
		i -= 1
	return buff

def rp_process(rplist):
	i = 0
	while len(rplist) != 1:
		if rplist[i] == '<<':
			rplist[i-1] = rp_reverse(rplist[i-1])
			del rplist[i]
		elif rplist[i] == '+':
			rplist[i-2] = ''.join([rplist[i-2], rplist[i-1]])
			i -= 1
			del rplist[i]
			del rplist[i]
		else:
			i += 1
	return rplist[0]


###		TEST CASE

test_sample_1 = '12((34)5(67)8)90'
test_sample_2 = 'a(bc)(de)'
test_sample_3 = '((abc)def)'

print 'sample 1:', test_sample_1
print 'result: (test_1) ', rp_process(rp_parse(test_sample_1))
print 'expected result: (test_1): 12 ( 43 5 76 8 ) 90 => 12 867534 90\n'

print 'sample 2:', test_sample_2
print 'result: (test_2) ', rp_process(rp_parse(test_sample_2))
print 'expected result: (test_2): acbde\n'

print 'sample 3:', test_sample_3
print 'result: (test_3) ', rp_process(rp_parse(test_sample_3))
print 'expected result: (test_3): fedabc\n'

if len(sys.argv) != 1:
	for i in sys.argv[1:]:
		print i, ':', rp_process(rp_parse(i))