OCaml function to evaluate arithmetic expressions

Question

I’ve written part of a mathematical calculator program. I’ve finished the parser of the program, so when a user types in a mathematical expression as a string, I already have a way to obtain a corresponding data structure of the following type:

type expression =
| Term of int
| Addition of expression * expression
| Multiplication of expression * expression
| Subtraction of expression * expression

All I need now is a way to evaluate these kinds of data structures.

(a) Write the expression corresponding to the mathematical statement “3*((1 + 4)- 5).”

(b) Extend the Ocaml datatype to include a Factorial constructor, so that it can handle expressions like “3*((1 + 4)! -5).”

(c) Write an Ocaml function eval which takes a mathematical expression and returns its (integer) value. For example, it should return 0 as the result from the expression in part (a).

 # let rec eval expr = ...
 val eval : expression -> int = <fun>

You may want to write a factorial Ocaml function to help out with the new Factorial constructor.

I'm confused about part a. Does it mean let expression = 3*((1 + 4)- 5);?

For part b, should I follow the pattern |Factorial of expression * expression?

Seems like you're asking for a lot of help with what looks like homework. You need to show what you've tried, we don't want to take the benefit out of it for you. For what it's worth, part (a) seems to be asking for an OCaml expression using the constructors Term, Addition, and Multiplication. — Jeffrey Scofield
Please don't vandalize your own posts. When you post here, you give SO the right to distribute the content under CC-by SA 4.0. Any vandalism will be reverted. — greg-449
If you continue to vandalize your question it will be locked by a moderator. — greg-449

Stefan Holdermans Stefan Holdermans · Accepted Answer · 2012-08-15T22:54:08

What is meant in a) is that you can now write mathematical expressions as values of the provided datatype expression. For example, the constructor Addition expresses that the addition operator (normally written as (+)) forms an expression by taking two smaller expressions as operands. So, for instance, the mathematical expression 2 + 3 can be represented by the Caml value

Addition (Term 2,Term 3)

Now, observing that the factorial operator takes one argument rather than two arguments, you should be able to extend the datatype expression with a constructor for factorials as is asked in b).

Finally, in c), writing an evaluation function for this kind of expression types is straightforward: constants just map to the integer value they are carrying and evaluating an addition involves recursively evaluating the operands of the addition and then adding them up:

let rec eval = function
  | Term n -> n
  | Addition (l,r) -> eval e1 + eval e2
  | ...

The remaining cases (for the remaining constructors, including the one for the constructor for factorials that you will add for b)) are analogous and you should be able to do that by yourself now.

Good luck!

OCaml function to evaluate arithmetic expressions

2 Answers