Not hard to know it is simply transform from in-order to post-order.
My first idea is to build a tree from in-order string and then traverse the tree by post-order - naive so slow.
Subtle stack manipulation solves it - stack only for operators:
http://cs.nyu.edu/courses/Fall12/CSCI-GA.1133-002/notes/InfixToPostfixExamples.pdf
BTW, I love Ruby more.
# SPOJ #4 QNR cnt = gets
cnt = cnt.to_i #
def process(str)
stk = []
i = 0
while i < str.length do
c = str[i]
case c
when 'a'..'z'
print c
when '+', '-'
stk.push(c)
when '*', '/'
while !stk.empty? && (stk.last != '+' or stk.last != '-') do
if(stk.last == '(')
break
end
print stk.pop()
end
stk.push(c)
when '^'
while !stk.empty? && stk.last == '^' do
if(stk.last == '(')
break
end
print stk.pop()
end
stk.push(c)
when '('
stk.push(c)
when ')'
while !stk.empty? && stk.last != '(' do
if(stk.last == '(')
break
end
print stk.pop()
end
if(stk.last == '(')
stk.pop()
end
end
i += 1
end
while !stk.empty? do
print stk.pop()
end
puts
end # def process i = 0
while i < cnt do
str = gets.to_s.downcase
process(str)
i += 1
end