Reverse Polish Notation (RPN) is a mathematical notation where every operator follows all of its operands. For instance, to add three and four, one would write "3 4 +" rather than "3 + 4". If there are multiple operations, the operator is given immediately after its second operand; so the expression written "3 − 4 + 5" would be written "3 4 − 5 +" first subtract 4 from 3, then add 5 to that.

Transform the algebraic expression with brackets into RPN form. 

You can assume that for the test cases below only single letters will be used, brackets [] will not be used and each expression has only one RPN form (no expressions like a*b*c)

----- Sample Input 1 ------ 
3
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))

----- Sample Output 1 ------ 
abc*+
ab+zx+*
at+bac++cd+^*

Source: codechef | Difficulty: EASY
Tags: Data structures


Solutions:
def main(string):
	stack = []
	s = ''
	for _ in string:
		if ord(_) in range(97, 123):
			s += _
		elif _ == ')':
			if stack != []:
				s += stack[-1]
				del stack[-1]
		elif _ == '(':
			continue
		else:
			stack.append(_)
	print(s)
for _ in range(int(input())):
	t = str(input())
	main(t)


n = int(input())
precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
for i in range(n):
	stack = []
	postflix = []
	x = input()
	for i in x:
		if i.isalpha():
			postflix.append(i)
		elif i == '(':
			stack.append(i)
		elif i == ')':
			while stack and stack[-1] != '(':
				postflix.append(stack.pop())
			stack.pop()
		elif i in precedence:
			while stack and stack[-1] != '(' and (precedence[i] <= precedence[stack[-1]]):
				postflix.append(stack.pop())
			stack.append(i)
	while stack:
		m = stack.pop()
		if m != '(':
			postflix.append(m)
	seperator = ''
	print(seperator.join(postflix))


def solution(expression):
	precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
	stack = []
	output = []
	for char in expression:
		if char.isalnum():
			output.append(char)
		elif char in '+-*/^':
			while stack and precedence[char] <= precedence.get(stack[-1], 0):
				output.append(stack.pop())
			stack.append(char)
		elif char == '(':
			stack.append(char)
		elif char == ')':
			while stack and stack[-1] != '(':
				output.append(stack.pop())
			stack.pop()
	while stack:
		output.append(stack.pop())
	return ''.join(output)
T = int(input())
for _ in range(T):
	expression = input()
	print(solution(expression))


for _ in range(int(input())):
	exp = input()
	stack = []
	s = ''
	for i in exp:
		if i.isalpha():
			s += i
		elif i == ')':
			for j in stack[::-1]:
				if j == '(':
					stack.pop()
					break
				s += stack.pop()
		else:
			stack.append(i)
	print(s)


n = int(input())
for i in range(n):
	output = []
	operator = []
	priority = {'(': 0, '^': 1, '*': 2, '/': 2, '+': 3, '-': 3}
	ag = input()
	for ch in ag:
		if ch == '(':
			operator.append(ch)
		elif ch == ')':
			while operator[-1] != '(':
				ele = operator.pop()
				output.append(ele)
			operator.pop()
		elif ch == '^' or ch == '*' or ch == '/' or (ch == '-') or (ch == '+'):
			if len(operator) > 0:
				while len(operator) > 0 and priority[operator[-1]] >= priority[ch]:
					ele = operator.pop()
					output.append(ele)
			operator.append(ch)
		else:
			output.append(ch)
	while len(operator) != 0:
		ele = operator.pop()
		output.append(ele)
	print(''.join(output))


for _ in range(int(input())):
	t = []
	st = []
	for i in input():
		if i.isalpha():
			t.append(i)
		elif i == ')':
			t.append(st.pop())
		elif i == '(':
			pass
		else:
			st.append(i)
	print(''.join(t))


def precedence(operator):
	if operator == '^':
		return 4
	elif operator in '*/':
		return 3
	elif operator in '+-':
		return 2
	elif operator == '(':
		return 1
t = int(input())
for _ in range(t):
	expression = input().strip()
	stack = []
	for char in expression:
		if char.isalpha():
			print(char, end='')
		elif char in '+-*/^':
			while stack and stack[-1] != '(' and (precedence(stack[-1]) >= precedence(char)):
				print(stack.pop(), end='')
			stack.append(char)
		elif char == '(':
			stack.append(char)
		elif char == ')':
			while stack and stack[-1] != '(':
				print(stack.pop(), end='')
			if stack and stack[-1] == '(':
				stack.pop()
	while stack:
		print(stack.pop(), end='')
	print()


T = int(input())
for _ in range(T):
	e = input()
	(rpn, rpn_) = ([], [])
	for i in e:
		if i.isalpha():
			rpn.append(i)
		elif i == ')':
			rpn.append(rpn_.pop())
		elif i == '(':
			pass
		else:
			rpn_.append(i)
	print(''.join(rpn))


for _ in range(int(input())):
	x = input()
	revpol = ''
	stk = []
	for i in x:
		if i.isalpha():
			revpol += i
		elif i in ('(', '+', '-', '/', '*', '^'):
			stk.append(i)
		else:
			while stk[-1] != '(':
				revpol += stk.pop(-1)
			stk.pop(-1)
	while stk:
		revpol += stk.pop(-1)
	print(revpol)


t = int(input())
for i in range(t):
	s = input()
	n = len(s)
	a = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
	l = []
	l2 = []
	ls = []
	for j in range(n):
		l.append(s[j])
	for k in range(n):
		x = l[k]
		if x in a:
			l2.append(l[k])
		elif x == ')':
			l2.append(ls.pop())
		elif x == '(':
			continue
		else:
			ls.append(l[k])
	output = ''
	for m in l2:
		output += m
	print(output)


def mine(L):
	n = len(L)
	ans = ''
	i = 1
	count_str = ''
	count_int = 0
	while i < n and L[i] != ')':
		count_int += 1
		if L[i] == '(':
			var = mine(L[i:])
			ans += var[0]
			count_int += var[1] + 1
			i += var[1] + 2
		else:
			if L[i] in 'abcdefghijklmnopqrstuvwxyz':
				ans += L[i]
			else:
				count_str = L[i]
			i += 1
	return (ans + count_str, count_int)
for i in range(int(input())):
	print(mine(input())[0])


t = int(input())
for j in range(t):
	rpn = ''
	stack = []
	for i in input():
		if i.isalpha():
			rpn += i
		elif i == ')':
			rpn += stack.pop()
			stack.pop()
		else:
			stack.append(i)
	print(rpn)


for inputs in range(int(input())):
	rpn = ''
	stack = []
	for i in input():
		if i.isalpha():
			rpn += i
		elif i == ')':
			rpn += stack.pop()
			stack.pop()
		else:
			stack.append(i)
	print(rpn)


def rpn(exp):
	line = []
	for i in range(len(exp)):
		line += exp[i]
	length = len(line)
	while i < len(line):
		if line[i] == ')':
			j = i
			while line[i] != '(':
				i -= 1
			line[i + 1] = line[i + 1] + line[i + 3] + line[i + 2]
			line.pop(i)
			line.pop(i + 1)
			line.pop(i + 1)
			line.pop(i + 1)
		i += 1
	return line[0]
cases = int(input())
while cases > 0:
	exp = input()
	print(rpn(exp))
	cases -= 1


for _ in range(int(input())):
	s = input()
	si = []
	a = ['+', '-', '*', '/', '^']
	for i in s:
		if i not in a and i != '(' and (i != ')'):
			print(i, end='')
		elif i in a:
			si.append(i)
		elif i == ')':
			print(si.pop(), end='')
	print()


for i in range(int(input())):
	IN = input()
	c = ['+', '-', '*', '/', '^']
	stack = []
	for i in IN:
		if i not in c and i != '(' and (i != ')'):
			print(i, end='')
		elif i in c and i != ')':
			stack.append(i)
		elif i == ')':
			print(stack.pop(), end='')
	print()


for t in range(int(input())):
	s = input()
	s1 = ' '
	l = []
	for i in s:
		if i == '(':
			pass
		elif 97 <= ord(i) <= 122:
			s1 += i
		elif i == ')':
			s1 += l[-1]
			l.pop(-1)
		else:
			l.append(i)
	print(s1)


def exp():
	s = input()
	l1 = []
	l2 = []
	for i in s:
		if i.isalpha():
			l1.append(i)
		elif i == ')':
			l1.append(l2.pop())
		elif i == '(':
			pass
		else:
			l2.append(i)
	print(''.join(l1))
a = int(input())
for i in range(a):
	exp()


def test():
	s = input()
	lst1 = []
	lst2 = []
	for i in s:
		if i.isalpha():
			lst1.append(i)
		elif i == ')':
			lst1.append(lst2.pop())
		elif i == '(':
			pass
		else:
			lst2.append(i)
	print(''.join(lst1))
t = int(input())
for _ in range(t):
	test()


for i in range(int(input())):
	s = input()
	n = len(s)
	s1 = ''
	s2 = ''
	for i in range(0, n):
		if s[i] >= 'a' and s[i] <= 'z':
			s1 += s[i]
		elif s[i] == '+' or s[i] == '-' or s[i] == '*' or (s[i] == '/') or (s[i] == '^'):
			s2 += s[i]
		elif s[i] == ')':
			s1 = s1 + s2[-1]
			s2 = s2[0:len(s2) - 1]
	print(s1)


def test():
	lis = []
	lis1 = []
	for i in input():
		if i.isalpha():
			lis.append(i)
		elif i == ')':
			lis.append(lis1.pop())
		elif i == '(':
			pass
		else:
			lis1.append(i)
	print(''.join(lis))
t = int(input())
for _ in range(t):
	test()


try:
	for _ in range(int(input())):
		exp = input()
		ans = []
		oper = []
		for i in list(exp):
			if i.isalpha():
				ans.append(i)
			elif i == ')':
				x = oper.pop(len(oper) - 1)
				while x != '(':
					ans.append(x)
					x = oper.pop(len(oper) - 1)
			else:
				oper.append(i)
		print(*ans, sep='')
except:
	pass


test_cases = int(input())
for _ in range(0, test_cases):
	input_string = input()
	my_list = []
	for str_val in input_string:
		if str_val == ')':
			second_operand = my_list.pop()
			operator = my_list.pop()
			first_operand = my_list.pop()
			my_list.pop()
			current_string = first_operand + second_operand + operator
			my_list.append(current_string)
		else:
			my_list.append(str_val)
	print(''.join(my_list))


for i in range(int(input())):
	lis = []
	lis1 = []
	for i in input():
		if i.isalpha():
			lis.append(i)
		elif i == ')':
			lis.append(lis1.pop())
		elif i == '(':
			pass
		else:
			lis1.append(i)
	print(''.join(lis))


def to_rpn(expression):
	precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
	operator_stack = []
	rpn = ''
	for char in expression:
		if char.isalpha():
			rpn += char
		elif char in precedence:
			while operator_stack and operator_stack[-1] != '(' and (precedence[char] <= precedence[operator_stack[-1]]):
				rpn += operator_stack.pop()
			operator_stack.append(char)
		elif char == '(':
			operator_stack.append(char)
		elif char == ')':
			while operator_stack and operator_stack[-1] != '(':
				rpn += operator_stack.pop()
			if operator_stack and operator_stack[-1] == '(':
				operator_stack.pop()
	while operator_stack:
		rpn += operator_stack.pop()
	return rpn
t = int(input())
for i in range(t):
	expression = input().strip()
	print(to_rpn(expression))


t = int(input())
for _ in range(t):
	debo = input()
	stack = []
	expression = []
	for i in debo:
		if i in ('+', '*', '-', '/', '^'):
			stack.append(i)
		elif i == '(':
			continue
		elif i == ')':
			expression.append(stack.pop())
		else:
			expression.append(i)
	print(''.join(expression))


d = {'+': 1, '-': 2, '*': 3, '/': 4, '^': 5}
r = '+-*/^'
t = int(input())
for i in range(t):
	w = []
	p = []
	s = input().strip()
	for j in s:
		if j == '(':
			w.append('(')
		elif j in r:
			w.append(j)
		elif j == ')':
			t = []
			while w[-1] != '(':
				t.append(w.pop())
			w.pop()
			p.extend(t)
		else:
			p.append(j)
	p.extend(reversed(w))
	for m in p:
		print(m, end='')
	print()


n = int(input())
for i in range(n):
	s = input()
	l = []
	for i in s:
		if i.isalnum():
			print(i, end='')
		elif i == '(':
			pass
		elif i == ')':
			print(l.pop(), end='')
		else:
			l.append(i)
	print(end='\n')


for _ in range(int(input())):
	s = input()
	p = []
	t = ''
	top = 0
	count = 0
	for i in range(len(s)):
		if s[i] == '(':
			p.append(s[i])
			top += 1
			count += 1
		if s[i] == ')':
			p.append(s[i])
			top += 1
			count -= 1
			while top > 0:
				if p[top - 1] == '(':
					break
				if p[top - 1] == ')' or p[top - 1] == '(':
					p.pop(top - 1)
				else:
					t += p.pop(top - 1)
				top -= 1
			p.pop(top - 1)
			top -= 1
		elif s[i].isalpha():
			t += s[i]
		elif s[i] == '+' or s[i] == '-' or s[i] == '*' or (s[i] == '^') or (s[i] == '/'):
			if top == 0:
				p.append(s[i])
				top += 1
			elif p[top - 1] == '^' and (s[i] == '+' or s[i] == '-' or s[i] == '*' or (s[i] == '^') or (s[i] == '/')):
				t += s[top - 1]
				p.pop()
				top -= 1
				p.append(s[i])
				top += 1
			elif (p[top - 1] == '*' or p[top - 1] == '/') and (s[i] == '+' or s[i] == '-' or s[i] == '*' or (s[i] == '^') or (s[i] == '/')):
				t += p.pop()
				top -= 1
				p.append(s[i])
				top += 1
			else:
				p.append(s[i])
				top += 1
	while top > 0:
		t += p[top - 1]
		top -= 1
	print(t)


for _ in range(int(input())):
	expression = input()
	stack = []
	for i in expression:
		if i == ')':
			while stack[-1] != '(':
				print(stack.pop(), end='')
			stack.pop()
		elif i in '+-*/^':
			stack.append(i)
		elif i == '(':
			stack.append(i)
		else:
			print(i, end='')
	print()


def is_operator(c):
	return c in '+-*/^'

def to_rpn(expr):
	stack = []
	output = ''
	for c in expr:
		if c.isalpha():
			output += c
		elif is_operator(c):
			while stack and is_operator(stack[-1]) and (c in '+-' or stack[-1] in '*/'):
				output += stack.pop()
			stack.append(c)
		elif c == '(':
			stack.append(c)
		elif c == ')':
			while stack and stack[-1] != '(':
				output += stack.pop()
			if stack and stack[-1] == '(':
				stack.pop()
	while stack:
		output += stack.pop()
	return output
t = int(input())
for _ in range(t):
	expr = input().strip()
	rpn = to_rpn(expr)
	print(rpn)


def transform(exprs):
	strlist = [i for i in exprs]
	u = int((strlist.count(')') + strlist.count('(')) / 2)
	iterate = [i % len(strlist) for i in range(len(strlist) * u)]
	c = 0
	k1 = 0
	k2 = 0
	k3 = 0
	for i in iterate:
		if strlist[i] == '(':
			if c == 0:
				k1 = i
			c += 1
			continue
		elif strlist[i] == ')':
			c -= 1
		if c == 1 and (strlist[i] == '+' or strlist[i] == '-' or strlist[i] == '*' or (strlist[i] == '/') or (strlist[i] == '^')):
			k2 = i
		elif c == 0 and strlist[i] == ')':
			k3 = i
			strlist[k3] = strlist[k2]
			strlist[k2] = ' '
			strlist[k1] = ' '
	for k in range(u * 2):
		strlist.remove(' ')
	exprs = ''
	for m in strlist:
		exprs += m
	return exprs
ui = int(input())
ul = []
for i in range(ui):
	k = input()
	ul.append(k)
for i in range(ui):
	k = transform(ul[i])
	print(k)


def infix_postfix(string):
	stack = []
	modified_string = ''
	for char in string:
		if char == '*' or char == '+' or char == '^' or (char == '-') or (char == '/'):
			stack.append(char)
		elif char == '(':
			continue
		elif char == ')' and stack:
			modified_string = modified_string + stack.pop()
		else:
			modified_string = modified_string + char
	return modified_string
testcases = int(input())
for i in range(testcases):
	string = str(input())
	print(infix_postfix(string))


dict = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 8, ')': 0, '(': 0}
s = int(input())
for i in range(s):
	string = input()
	stack = []
	for i in range(len(string)):
		if string[i] == '(':
			stack.append(string[i])
		elif string[i] == ')':
			while stack[len(stack) - 1] != '(':
				print(stack.pop(), end='')
			stack.pop()
		elif string[i] in dict:
			if dict[string[i]] > dict[stack[len(stack) - 1]]:
				stack.append(string[i])
			else:
				while dict[string[i]] <= dict[stack[len(stack) - 1]]:
					print(stack.pop(), end='')
				stack.append(string[i])
		else:
			print(string[i], end='')
	print()


for _ in range(int(input())):
	s = input()
	a = ' '
	oprends = {'*', '/', '+', '-', '^'}
	l = []
	for i in range(len(s) - 1):
		if s[i] == '(' or s[i] in oprends:
			l.append(s[i])
		elif s[i].isalpha():
			a += str(s[i])
		else:
			while l[-1] != '(':
				a += l.pop()
			l.pop()
	while l[-1] != '(':
		a += l.pop()
	print(a)


for _ in range(int(input())):
	s = input()
	ans = ''
	stack = []
	operator = ['+', '-', '*', '/', '^']
	for char in s:
		if char == '(':
			continue
		elif char in operator:
			stack.append(char)
		elif char == ')':
			x = stack.pop()
			ans += x
		else:
			ans += char
	print(ans)


for i in range(int(input())):
	x = input()
	stack = []
	a = ' '
	s = {'*', '/', '+', '-', '^'}
	for i in range(len(x) - 1):
		if x[i] == '(' or x[i] in s:
			stack.append(x[i])
		elif x[i].isalnum():
			a += str(x[i])
		else:
			while stack[-1] != '(':
				a += stack.pop()
			stack.pop()
	while stack[-1] != '(':
		a += stack.pop()
	print(a)


t = int(input())
for tc in range(t):
	x = input()
	l = []
	a = ' '
	s = {'*', '/', '+', '-', '^'}
	for i in range(len(x) - 1):
		if x[i] == '(' or x[i] in s:
			l.append(x[i])
		elif x[i].isalpha():
			a += str(x[i])
		else:
			while l[-1] != '(':
				a += l.pop()
			l.pop()
	while l[-1] != '(':
		a += l.pop()
	print(a)


for i in range(int(input())):
	s = input()
	stack = []
	b = ' '
	sui = {'*', '/', '+', '-', '^'}
	for i in range(len(s) - 1):
		if s[i] == '(' or s[i] in sui:
			stack.append(s[i])
		elif s[i].isalnum():
			b += str(s[i])
		else:
			while stack[-1] != '(':
				b += stack.pop()
			stack.pop()
	while stack[-1] != '(':
		b += stack.pop()
	print(b)