We work with arithmetic expressions over integers involving the operations addition (+), subtraction (-) and multiplication (*).
Arithmetic expressions are inherently ambiguous. For instance 1+2*3 could mean (1+2)*3 = 9 or 1+(2*3) = 7. Parentheses are one way to disambiguate expressions. Typically, we define a precedence among operators (the BODMAS rule from school arithmetic) to give a unique interpretation in the absence of parentheses.
Another way to write expressions unambiguously is to use expression trees. Here are the trees corresponding to the two interpretations of 1+2*3. Each integer is a leaf node and each operation is the root of a binary tree with its two arguments as children.
* +
/ \ / \
+ 3 1 *
/ \ / \
1 2 2 3
(1+2)*3 1+(2*3)
We can represent such a tree using a dictionary. A leaf node has a single key 'value', mapped to an integer. A non-leaf node has three keys: 'op' has a value from the set {'+','-','*'}, while 'arg1' and 'arg2' contain nested dictionaries corresponding to the expressions in the left and right subtrees.
Here are some expressions with their corresponding dictionary representations.
| Expression | Dictionary representation | ||||
|---|---|---|---|---|---|
| 99 | {'value':99} | ||||
| (7+8) | {'op': '+', 'arg1': {'value':7}, 'arg2': {'value':8}} | ||||
| (7+8)-(8*9) |
|
||||
| (7+8)*9 |
|
||||
| 7*(8+9) |
|
Write the following functions in Python. (Hint: Exploit the inductive structure of expressions to write recursive functions.)
validate(expr) returns True if its input is a valid dictionary representation of an expression and returns False otherwise.
evaluate(expr) takes as input a dictionary representation of an expression. The function returns the value of the expresssion as an int if the input is a valid expression and returns None otherwise.
display(expr) takes as input a dictionary representation of an expression. The function returns a string representation of the expression if the input is a valid expression, and returns None otherwise.
If the expression is an integer, the function should return the integer as a string. For non-trivial expressions, the function should return a string with enclosing parentheses — so 'e1 op e2' will be returned as '(e1 op e2)'.
Examples:display({'value':99}) returns '99'
display({'op':'+', 'arg1':{'value':7}, 'arg2':{'value':8}}) returns '(7+8)'
display({'op':'-', 'arg1': {'op':'+', 'arg1':{'value':7}, 'arg2':{'value':8}}, 'arg2': {'op':'*', 'arg1':{'value':8}, 'arg2':{'value':9}}}) returns '((7+8)-(8*9))'
Submit your solution through Moodle as a single Python notebook with solutions to all the questions.
Add documentation to explain at a high level what your code is doing.
Show some sample executions.