46 lines
1.1 KiB
Crystal
46 lines
1.1 KiB
Crystal
OPS = {
|
|
"^" => { prio: 4, assoc: :right },
|
|
"*" => { prio: 3, assoc: :left },
|
|
"/" => { prio: 3, assoc: :left },
|
|
"+" => { prio: 2, assoc: :left },
|
|
"-" => { prio: 2, assoc: :left },
|
|
}
|
|
|
|
def to_rpn (tokens)
|
|
output = [] of String | Float64
|
|
opstack = [] of String
|
|
|
|
tokens.each do |token|
|
|
case token
|
|
when .is_a?(Float64) then output << token
|
|
when "(" then opstack << token
|
|
when ")"
|
|
while opstack.present? && opstack.last != "("
|
|
output << opstack.pop
|
|
end
|
|
opstack.pop
|
|
else
|
|
opdata = OPS[token]? || raise "Unknown operator '#{token}'"
|
|
while opstack.present? && OPS.has_key?(opstack.last) &&
|
|
(opdata[:prio] < OPS[opstack.last][:prio] ||
|
|
opdata[:prio] == OPS[opstack.last][:prio] && opdata[:assoc] == :left)
|
|
output << opstack.pop
|
|
end
|
|
opstack << token
|
|
end
|
|
end
|
|
while opstack.present?
|
|
output << opstack.pop
|
|
end
|
|
output
|
|
end
|
|
|
|
def tokenize (s)
|
|
s.split.map {|t| t.to_f rescue t }
|
|
end
|
|
|
|
infix = tokenize "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"
|
|
rpn = to_rpn infix
|
|
|
|
puts infix.join(" ")
|
|
puts rpn.join(" ")
|