Programming Assignment 2

In this project, you will write a program that takes as input an arithmetic expression and should do the following:

Check that the expression is well formed: that means the number of opening parenthesis ( is equal to closing ones, the operands are numeric characters, the operators are +, -, * or /. Build the expression tree based on the arithmetic expression. This will take into consideration the priority of some operators over the others. Each node in the tree has as value a number or a string. In particular, leaf nodes have number values while intermediary nodes have a string value. Evaluate the outcome of the whole expression by traversing the tree (using one variant of depth-first search) starting with leaf nodes and evaluating each branch until you get the result.

Example: expression = (((9+1)/2)*3)-4

This expression is well-formed because the number of ( is equal to the number of ), operands are numeric characters and operators are the pre-defined ones For example, expression = (((9+1)/2)*3)-4))) is not a valid expression because it has extra ). Also expression = (((9+1)/2)*3)-a))) is not valid because a is alphabetical character. expression = (((9+1)/2)*3)&4))) is not valid because & is not among the pre-defined operators The resulting tree of expression = (((9+1)/2)*3)-4 would be:

To evaluate the outcome of this expression tree, you do a depth-first to retrieve 1, 9 and + to evaluate their outcome, then repeat that recursively until you evaluate the whole tree. The result would be expression = 11.