codepad

Language:

=begin
수식 트리 만들고 계산하기
후위 수식을 받아서 트리를 만들고 계산한다
중위 수식을 후위 수식으로 변경하는 것은 생략

=end

class ExpTreeNode
  attr_accessor :data, :left, :right

def initialize(data)
    @data = data
    @left = nil
    @right = nil
  end

end

class ExpTree

OPERATOR_LIST = ['+', '-', '*', '/']

def initialize
    @root = nil
  end

def load_postfix_expression(exp)
    expression = exp.clone

@root = build_expression_tree(expression)
  end

def calculate
    calculate_recursive(@root)
  end

private
 
  def build_expression_tree(exp, parent_node = nil, is_left = nil)
    # 표현식이 끝남
    return nil if 0 >= exp.length

# 표현식 끝을 토큰으로 가져오고 표현식에서 잘라버림
    data = exp.split(//)[exp.length - 1]
    exp.chop!

new_node = ExpTreeNode.new(data)

# 부모 노드가 지정된 경우 새 노드를 부모 노드에 붙임
    if parent_node
        is_left ? parent_node.left = new_node : parent_node.right = new_node
    end

# 연산자인 경우 피연산자 두 개를 얻음
    if OPERATOR_LIST.include?(data)
      new_node.right = build_expression_tree(exp, new_node, nil)
      new_node.left = build_expression_tree(exp, new_node, true)
    end

# 새 노드 리턴
    new_node
  end

def calculate_recursive( node )

# 연산자인 경우 피연산자 두 개를 얻어서 계산하고 리턴
    if OPERATOR_LIST.include?(node.data)
      operand1 = calculate_recursive(node.left)
      operand2 = calculate_recursive(node.right)

case node.data
      when '+'
        result = operand1.to_i + operand2.to_i
      when '-'
        result = operand1.to_i - operand2.to_i
      when '*'
        result = operand1.to_i * operand2.to_i
      when '/'
        result = operand1.to_i / operand2.to_i
      end
    else
      # 피연산자인 경우 자기 자신을 리턴
      result = node.data
    end

result
   
  end
 
end

exp_tree = ExpTree.new

exp_tree.load_postfix_expression("12*78-+")
puts exp_tree.calculate

exp_tree.load_postfix_expression("78*58*+2/32--")
puts exp_tree.calculate

Private [?]

Run code