48 lines
1.9 KiB
Lua
48 lines
1.9 KiB
Lua
-- Postfix notation is an alternative to the normal "infix" notation
|
|
-- used in mathematical expressions. Instead of writing the operator
|
|
-- between the operands, the operator comes after them. For example,
|
|
-- "1 + 2" is notated as "1 2 +". This removes the need for operator
|
|
-- precedence and parentheses: rather than having to resolve the
|
|
-- ambiguity of an expression like "1 + 2 * 3" with convention or
|
|
-- parentheses, the evaluation order is explicit -- multiplication-
|
|
-- first is "1 2 3 * +" and addition-first is "1 2 + 3 *".
|
|
--
|
|
-- As well as this notational convenience, postfix can be easily
|
|
-- evaluated using a stack. Whenever an operand is encountered, the
|
|
-- value is pushed onto the stack, and whenever an operator is
|
|
-- encountered, two values are popped from the stack and the result of
|
|
-- the operation is pushed on in their place. Finally, the value left
|
|
-- on the top of the stack is the result of the operation.
|
|
--
|
|
-- Write a function that will evaluate a postfix expression and return
|
|
-- the result. You can assume that the expression is valid, and not
|
|
-- worry about handling error cases. The operators will be "+", "-",
|
|
-- "*" and "/".
|
|
--
|
|
-- Solution --------------------------------------------------------------------
|
|
function evaluate_postfix(expression)
|
|
-- Your implementation here
|
|
end
|
|
|
|
-- Tests -----------------------------------------------------------------------
|
|
|
|
local luaunit = require("luaunit.luaunit")
|
|
|
|
function test_1_2_plus_3_times_is_9()
|
|
luaunit.assertEquals(evaluate_postfix("1 2 + 3 *"), 9)
|
|
end
|
|
|
|
function test_1_2_3_times_plus_is_7()
|
|
luaunit.assertEquals(evaluate_postfix("1 2 3 * +"), 7)
|
|
end
|
|
|
|
function test_4_6_plus_5_divide_2_1_minus_minus_is_1()
|
|
luaunit.assertEquals(evaluate_postfix("4 6 + 5 / 2 1 - -"), 1)
|
|
end
|
|
|
|
function test_12_2_times_6_divide_10_times_2_plus_is_42()
|
|
luaunit.assertEquals(evaluate_postfix("12 2 * 6 / 10 * 2 +"), 42)
|
|
end
|
|
|
|
os.exit(luaunit.LuaUnit.run())
|