(* Hope Crosier CPSC 3400 HW 5 All of the code you turn in must have been written by you without immediate reference to another solution to the problem you are solving. That means that you can look at other programs to see how someone solved a similar problem, but you shouldn't have any code written by someone else visible when you write yours (and you shouldn't have looked at a solution just a few seconds before you type!). You should compose the code you write based on your understanding of how the features of the language you are using can be used to implement the algorithm you have chosen to solve the problem you are addressing. Doing it this way is "real programming" - in contrast to just trying to get something to work by cutting and pasting stuff you don't actually understand. It is the only way to achieve the learning objectives of the course. I attest to the statement above *) /// Takes in a key x and a head value (y,z) to see if x and y are equal let checkChar (x: char) ((y,z): string*int) = let k = string(x) if k = y then true else false /// Takes in a head value (a,b) and returns only b let getChar ((a,b): string*int) = b /// takes a string and a list of bindings and returns the first value in the list /// bound to the key of the first character of the string let rec scanString (x: string) list = if list = [] then 0 else let hd :: tl = list // see if current hd values match key if (checkChar x.[0] hd) then // get the integer value from current hd getChar hd // otherwise ignore current hd and continue to rest of list else scanString x tl /// given a stack and an integer value, appends the integer onto the front of the stack let push stack x = x :: stack /// given a stack, pops the first value off the stack and returns it /// does not return the remaining stack since this function is intended to only /// be called when the expr has been fully evaluated let popAnswer stack = match stack with | [] -> -1 | hd :: tl -> hd /// given a stack, returns the top value and the remaining stack let pop stack = match stack with | [] -> (0, stack) | hd :: tl -> (hd, tl) /// given a stack, returns the top two values and the remaining stack let doublePop stack = match stack with | [] -> (0, 0, stack) //check not a number | hd1 :: hd2 :: tl -> (hd1, hd2, tl) /// given a list of variable bindings and a string expression, recursively evaluates the /// answer of the expression based on the symbols, letters, and appropriate bindings /// from the string expression let eval vars expr = let rec innerEval vars stack (expr: string) = if expr = "" then popAnswer stack else match expr.[0] with // if there is a space in the string, ignore it | ' ' -> innerEval vars stack expr.[1..] // create new binding based on value on top of stack | '@' -> let letter = string(expr.[1]) let num, newStack = pop stack let newVars = (letter,num)::vars innerEval newVars newStack expr.[2..] // swaps the position of the top two values on the stack | '$' -> let num1, num2, tempStack = doublePop stack let temp2Stack = push stack num1 let newStack = push temp2Stack num2 innerEval vars newStack expr.[1..] // adds the top two vales on the stack | '+' -> let (num1: int), (num2: int), tempStack = doublePop stack let newStack = push tempStack (num1 + num2) innerEval vars newStack expr.[1..] // subtracts the top two values on the stack | '-' -> let num1, num2, tempStack = doublePop stack let newStack = push tempStack (num2 - num1) innerEval vars newStack expr.[1..] // multiplies the top two values on the stack | '*' -> let num1, num2, tempStack = doublePop stack let newStack = push tempStack (num1 * num2) innerEval vars newStack expr.[1..] // divides the top two values on the stack | '/' -> let num1, num2, tempStack = doublePop stack let newStack = push tempStack (num1 / num2) innerEval vars newStack expr.[1..] // catch all case when there is a letter in the string to add matching value of // to stack | _ -> // add integer binding from character to stack innerEval vars (push stack (scanString expr vars)) expr.[1..] innerEval vars [] expr let testEval = eval [("a",5);("b",2);("c",9)] let exprList = [ "ca- @b bc$-"; "bbb @q bqbq*****"; "ab-ab*ab+--" ] let resultList = List.map testEval exprList printfn "%A" resultList