fork(2) download
copy 
  1. #!/usr/bin/python
  2.  
  3. import os
  4. import sys
  5.  
  6. def rp_parse(string):
  7.  
  8. 	# Stage 1: create expression
  9. 	string = string.replace('(', '+(').replace(')', ')+')
  10. 	while string != string.replace('(+(', '((').replace(')+)', '))').replace('++', '+'):
  11. 		string = string.replace('(+(', '((').replace(')+)', '))').replace('++', '+')
  12. 	if string[0] == '+':
  13. 		string = string[1:]
  14. 	if string[len(string)-1] == '+':
  15. 		string = string[:len(string)-1]
  16.  
  17. 	# Stage 2: reverse_polish_notation(string)
  18. 	#	Priority: 1: '()' ; 2: '+'
  19. 	#	Alias: '()' => '<<'
  20. 	op_stack  = list()
  21. 	out_stack = list()
  22. 	counter   = 0
  23. 	out_stack.append('')
  24. 	for c in string:
  25. 		if c == '(':
  26. 			op_stack.append('(')
  27. 			if out_stack[counter]:
  28. 				out_stack.append('')
  29. 				counter += 1
  30. 		elif c == ')':
  31. 			i = len(op_stack) - 1
  32. 			while op_stack[i] != '(' and i >= 0:
  33. 				out_stack.append(op_stack[i])
  34. 				op_stack.pop()
  35. 				counter += 1
  36. 				i -= 1
  37. 			op_stack.pop()	# take '(' out
  38. 			if out_stack[counter] == '':
  39. 				out_stack[counter] = "<<"
  40. 				out_stack.append('')
  41. 				counter += 1
  42. 			else:
  43. 				out_stack.append('<<')
  44. 				out_stack.append('')
  45. 				counter += 2
  46. 		elif c == '+':
  47. 			op_stack.append('+')
  48. 			if out_stack[counter]:
  49. 				out_stack.append('')
  50. 				counter += 1
  51. 		else:
  52. 			out_stack[counter] += c
  53.  
  54. 	if out_stack[counter] == '':
  55. 		del out_stack[counter]
  56.  
  57. 	i = len(op_stack) - 1
  58. 	while i >= 0:
  59. 		out_stack.append(op_stack[i])
  60. 		i -= 1
  61.  
  62. 	return out_stack
  63.  
  64.  
  65. def rp_reverse(string):
  66. 	i = len(string) - 1
  67. 	buff = str()
  68. 	while i >= 0:
  69. 		buff += string[i]
  70. 		i -= 1
  71. 	return buff
  72.  
  73. def rp_process(rplist):
  74. 	i = 0
  75. 	while len(rplist) != 1:
  76. 		if rplist[i] == '<<':
  77. 			rplist[i-1] = rp_reverse(rplist[i-1])
  78. 			del rplist[i]
  79. 		elif rplist[i] == '+':
  80. 			rplist[i-2] = ''.join([rplist[i-2], rplist[i-1]])
  81. 			i -= 1
  82. 			del rplist[i]
  83. 			del rplist[i]
  84. 		else:
  85. 			i += 1
  86. 	return rplist[0]
  87.  
  88.  
  89. ###		TEST CASE
  90.  
  91. test_sample_1 = '12((34)5(67)8)90'
  92. test_sample_2 = 'a(bc)(de)'
  93. test_sample_3 = '((abc)def)'
  94.  
  95. print 'sample 1:', test_sample_1
  96. print 'result: (test_1) ', rp_process(rp_parse(test_sample_1))
  97. print 'expected result: (test_1): 12 ( 43 5 76 8 ) 90 => 12 867534 90\n'
  98.  
  99. print 'sample 2:', test_sample_2
  100. print 'result: (test_2) ', rp_process(rp_parse(test_sample_2))
  101. print 'expected result: (test_2): acbde\n'
  102.  
  103. print 'sample 3:', test_sample_3
  104. print 'result: (test_3) ', rp_process(rp_parse(test_sample_3))
  105. print 'expected result: (test_3): fedabc\n'
  106.  
  107. if len(sys.argv) != 1:
  108. 	for i in sys.argv[1:]:
  109. 		print i, ':', rp_process(rp_parse(i))
  110.  
  111.  
  112.  
Success #stdin #stdout 0s 9024KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
sample 1: 12((34)5(67)8)90
result: (test_1)  1286753490
expected result: (test_1): 12 ( 43 5 76 8 ) 90 => 12 867534 90

sample 2: a(bc)(de)
result: (test_2)  acbed
expected result: (test_2): acbde

sample 3: ((abc)def)
result: (test_3)  fedabc
expected result: (test_3): fedabc
https://ideone.com/5k7mAd
language:
Python (cpython 2.7.16)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!