***MUST BE IN C++***

Instructions: In this programming assignment, you will implement a calculator. The user will first input an expression or several expressions from stdio. Then your calculator should evaluate the expressions and give correct results. You need to use some data structures and their operations to implement the calculator.

You will be given a file with a list of triplets. You will construct a binary tree from the triplets. The triplet file will have the format as in the following example:

10 5

0 1 2

1 3 4

2 5 6

3 7 8

4 9 -1

5 -1 -1

6 -1 -1

7 -1 -1

8 -1 -1

9 -1 -1

that is, the file will have n + 1 lines. The first line has two numbers. The first number is the number of nodes in the binary tree that you will construct. The second number is the size of hash table that you will be using during the tree construction. In the above example, the tree will have 10 nodes, and the hash table will have an array of size 5. In the rest n lines, there is three numbers in each line. The first number is the parent node ID, the second number is the left child node ID, the third number is the right child node ID. For example, in the line of 0 1 2, the node 0 is the parent of node 1 and node 2, and node 1 is the left child of node 0, node 2 is the right child of node 2. If a node does not have a left/right child, then the second/third number will be -1. For example, in the line of 4 9 -1, the node 4 has only a left child (node 9) but has not a right child. In the line of 9 -1 -1, the node 9 does not have a left or a right child. You will implement some classes described as follows. Please note that all the following code is pseudo-code. The arguments and their data types of the function, and the output and its data type of the function are fully up to you, as long as you implement the functionality of the function as it should have and the function has the name as required. You can also define different specifiers (private, public, protected; friend) for the variables and functions as needed. The functions and variables listed below are the required ones that you need to implement in order to get points. However, you may need to have some other functions or variables that may help implement the required functions.

1.) (75 points) You will implement a BinaryTree class:

2.) (10 points) Implement a BinaryTreeNode class

3.) (30 points) Implement a Hash class.

4.) (10 points) You need to allow users to input the file name of the triplets, for example, ./buildBinaryTree inputfile.txt