stack-calculator.rb

stack-calculator.rb

ORDER = {
  '$' => 1,
  '-' => 2,
  '+' => 3,
  '*' => 4,
  '/' => 5,
}

OPERATOR = {
  '-' => -> (a, b) {a - b},
  '+' => -> (a, b) {a + b},
  '*' => -> (a, b) {a * b},
  '/' => -> (a, b) {a / b},
}

def calc(expr)
  operands = []
  operators = []
  expr << '$'
  while e = expr.shift
    unless (q = ORDER[e])
      operands.push(e.to_i)
      next
    end
    while (operators.length > 0) && (ORDER[operators[-1]] >= q)
      a1 = operands.pop
      a2 = operands.pop
      op = operators.pop
      v = {op: op, l: a1, r: a2}
      operands.push(v)
    end
    operators.push(e)
  end
  operands.pop
end

def traverse(expr)
  return expr if expr.is_a? Numeric
  a1 = traverse(expr[:l]) if (a1 = expr[:l]).is_a? Hash
  a2 = traverse(expr[:r]) if (a2 = expr[:r]).is_a? Hash
  OPERATOR[expr[:op]].(a1, a2)
end

v = calc('1+2*3/4+3-5'.chars)
p traverse(v)