逆波蘭記法計算機

備忘録。

Haskell

operate :: [Integer] -> String -> [Integer]
operate (r:l:st) "+" = (l + r):st
operate (r:l:st) "-" = (l - r):st
operate (r:l:st) "*" = (l * r):st
operate (r:l:st) "/" = (l `div` r):st
operate stack    t   = (read t::Integer):stack

rpn :: String -> Integer
rpn s = case foldl operate [] (words s) of [answer] -> answer

$ ghci
Prelude> :l rpn.hs
*Main> rpn "12 32 + 4 / 1 - 10 *"
100

Ruby

def rpn(s)
  stack = []
  s.split.each do |token|
    if '+-*/'.include? token
      l, r = stack.pop(2)
      stack.push token.to_sym.to_proc[l, r]
    else
      stack.push token.to_i
    end
  end
  stack.last # 脇が甘い
end

$ irb
irb(main):001:0> require './rpn.rb'
=> true
irb(main):002:0> rpn '12 32 + 4 / 1 - 10 *'
=> 100

Prolog

words([], []) :- !.
words(S, [L|RS]) :- append(L, [0' |R], S), words(R, RS), !.
words(S, [S]) :- !.

rpn([], [Answer], Answer).
rpn(["+"|Tokens], [R,L|Stack], Answer) :- N is L + R, rpn(Tokens, [N|Stack], Answer).
rpn(["-"|Tokens], [R,L|Stack], Answer) :- N is L - R, rpn(Tokens, [N|Stack], Answer).
rpn(["*"|Tokens], [R,L|Stack], Answer) :- N is L * R, rpn(Tokens, [N|Stack], Answer).
rpn(["/"|Tokens], [R,L|Stack], Answer) :- N is L / R, rpn(Tokens, [N|Stack], Answer).
rpn([T|Tokens], Stack, Answer) :- number_codes(N, T), rpn(Tokens, [N|Stack], Answer).

rpn(S, Anser) :- words(S, Tokens), rpn(Tokens, [], Anser), !.

$ swipl --traditional

?- ['rpn.prolog'].
true.

?- rpn("12 32 + 4 / 1 - 10 *", N).
N = 100.