전위 표기를 후위 표기로 변환(prefix to postfix)

2011년 3월 28일 월요일

#!/usr/bin/ruby
# coding: utf-8

# 전위 표기(prefix)에서 후위 표기(postfix)로 변환

prefix = '+ * / A ^ B C D E'.split # 입력된 전위 표기 배열
postfix = [] # 후위 표기 출력용 배열

index = 0 # 후위 표기 배열 인덱스
stack = [] # 연산자 스택

for element in prefix
    if element =~ /[+\-\*\/\^]/
        stack.push(element)
    else
        postfix[index] = element
        index = index + 1

        # first 는 bottom, last 는 top
        while (not stack.empty?) and (stack.last.eql? :left_done)
            raise 'error 1' if stack.pop.nil?
            postfix[index] = stack.last
            index = index + 1
            raise 'error 2' if stack.pop.nil?
        end # end of while

        stack.push(:left_done)
    end # end of case
end # end of for

p prefix.join(" ")  #=> "+ * / A ^ B C D E"
p postfix.join(" ") #=> "A B C ^ / D