Reverse Polish Notation Calculator : Functional Programming

Reverse Polish Notation Calculator : Functional Programming


 What is Reverse Polish Notation?
Most of us are familiar with different arithmetic operators and their precedence. So When we try to solve the following equation, to avoid ambiguity, we make use of brackets, precedence and associativity:

A+B*C = ?
So without the brackets, this equation solves to (B*C) first then added to A. This seems easy on paper, but the problem in early days arose when people tried to implement these functionalities using a Calculator. How did they do it? This is where Polish mathematician Jan Lukasiewicz comes in. He showed that using a Postfix notation to write the expression instead of Infix will help us create a calculator that is capable of having precedence and associativity. PostFix notation simply means writing operators in front of their operands, instead of between them, brackets were made unnecessary.
Eg: 1+2*3 would be:


In the figure above, we made use of a data structure known as Stack. And we can easily implement this using a Procedural Programming Language. This project, however, makes use of Functional Programming Paradigm. In Functional Programming every computation is treated as the evaluation of a mathematical function. This avoids changing state and mutable data. The programming language used to implement this project is OCaml.
open Stdio
let stack = Stack.create ()
exception RPNFail
let rec compute input =
match input with
| [] ->
if Stack.length stack == 1 then
Stack.pop stack
else
raise RPNFail
| hd :: tl ->
begin
try
match hd with
| "+" ->
let op2 = Stack.pop stack in
let op1 = Stack.pop stack in
Stack.push (op1 +. op2) stack;
| "-" ->
let op2 = Stack.pop stack in
let op1 = Stack.pop stack in
Stack.push (op1 -. op2) stack;
| "*" ->
let op2 = Stack.pop stack in
let op1 = Stack.pop stack in
Stack.push (op1 *. op2) stack;
| "/" ->
let op2 = Stack.pop stack in
let op1 = Stack.pop stack in
Stack.push (op1 /. op2) stack;
| "^" ->
let op2 = Stack.pop stack in
let op1 = Stack.pop stack in
Stack.push (op1 ** op2) stack;
| token ->
let fl = Pervasives.float_of_string token in
Stack.push fl stack;
with Stack.Empty
-> raise RPNFail
end
; compute tl
let () =
while true do
try let line = read_line () in
let strList = Str.split (Str.regexp " +") line in
try
printf "%f\n" (compute strList)
with RPNFail
-> printf "Invalid computation\n"
with End_of_file
-> ()
done;

You can find the entire code  here, in my Github repo.