Skip to content

Instantly share code, notes, and snippets.

@jbpotonnier

jbpotonnier/posfix.ml

Last active Oct 12, 2015
Embed
What would you like to do?
Postfix evaluation
let push : float list -> string -> float list =
fun stack input -> match stack, input with
| (b::a::rest), "+" -> a +. b::rest
| (b::a::rest), "-" -> a -. b::rest
| (b::a::rest), "*" -> a *. b::rest
| (b::a::rest), "/" -> a /. b::rest
| rest, number -> (float_of_string number)::rest
let polish_eval : string -> float =
fun input ->
let words = Str.split (Str.regexp " +") in
List.hd (List.fold_left push [] (words input))
let all = List.fold_left (&&) true in
all [
float_of_int 3 = polish_eval "1 2 +";
4.0 = polish_eval "2 2 +";
1.0 = polish_eval "-4 5 +";
1.0 = polish_eval "3 2 -";
4.0 = polish_eval "3 2 1 - +";
1.5 = polish_eval "3 2 /";
2.0 = polish_eval "4 2 5 * + 1 3 2 * + /";
14.0 = polish_eval "5 1 2 + 4 * 3 - +"
]
import Test.HUnit
push :: [Double] -> String -> [Double]
push (b:a:stack) "+" = a + b:stack
push (b:a:stack) "-" = a - b:stack
push (b:a:stack) "*" = a * b:stack
push (b:a:stack) "/" = a / b:stack
push stack number = read number:stack
polish_eval :: String -> Double
polish_eval = head . foldl push [] . words
main = runTestTT $ test [
"addition" ~:
test [
3 ~=? polish_eval "1 2 +",
4 ~=? polish_eval "2 2 +",
1 ~=? polish_eval "-4 5 +"
],
"soustraction" ~:
test [
1 ~=? polish_eval "3 2 -",
4 ~=? polish_eval "3 2 1 - +"
],
"division" ~:
test [
1.5 ~=? polish_eval "3 2 /"
],
"acceptance" ~:
test [
2 ~=? polish_eval "4 2 5 * + 1 3 2 * + /",
14 ~=? polish_eval "5 1 2 + 4 * 3 - +"
]
]
require "test/unit"
OPERATIONS = {
"+" => lambda { |a, b| a + b },
"-" => lambda { |a, b| a - b },
"*" => lambda { |a, b| a * b },
"/" => lambda { |a, b| a / b }
}
def push(stack, elem)
operation = OPERATIONS[elem]
if operation.nil?
[elem.to_f, *stack]
else
b, a, *rest = stack
[operation.call(a, b), *rest]
end
end
def eval_polish(expression)
expression.split.inject([]) { |stack, elem| push(stack, elem) }.pop
end
class PolishTest < Test::Unit::TestCase
def test_soustraction
assert_equal 1, eval_polish('3 2 -')
assert_equal 3, eval_polish('5 2 -')
end
def test_addition
assert_equal 5, eval_polish('3 2 +')
end
def test_addition_2_etages
assert_equal 6, eval_polish('3 2 1 + +')
end
def test_multiplication
assert_equal 6, eval_polish('3 2 *')
end
def test_division
assert_equal 2, eval_polish('4 2 /')
assert_equal 1.5 , eval_polish('3 2 /')
end
def test_acceptance
assert_equal 2, eval_polish('4 2 5 * + 1 3 2 * + /')
assert_equal 14, eval_polish('5 1 2 + 4 * 3 - +')
end
end
@jpcaruana

This comment has been minimized.

Copy link

@jpcaruana jpcaruana commented Oct 31, 2012

@jpcaruana

This comment has been minimized.

Copy link

@jpcaruana jpcaruana commented Dec 14, 2012

pour la version haskell, la ligne 8 est-elle vraiment nécessaire ?
push stack "" = stack

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.