JC1503 Object-Oriented Programming - Assessment2 - Expression Binary Tree
Introduction:
In Q1 of JC1503 Practical on Trees (Practical 10), you were given the following expression:
“(((5+2)*(2−1))/((2+9)+((7−2)−1))*8)”
and were asked to convert it to a binary tree.
In this assessment, you are asked to design a python program that can automatically convert a mathematical expression into a binary tree after the user enters it as an input. Specifically, the expression must be in the same format as the above, and a valid expression can be recursively defined as follows:
It must be in the form of (X?Y) where X and Y are either numbers or valid expressions, and ? stands for operators (*, /, +, -)
For instance,
(4*5) is a valid expression;
((2*3)*5) and ((2*4)*(5*6)) are also valid expressions;
(4*5*6) is not a valid expression because it has three operands within one pair of brackets; ((4*(5+6) is not a valid expression as the brackets are mismatched (final bracket missing).
To simplify the problem, we assume all numbers are single-digit ones (i.e., ranging from 0 to 9) and all operators are: *, /, +, -
Hint: You may want to use a combination of data structures, for instance, stacks and trees.
Tests
Writing test for your code is a good practice. Therefore, some unit tests should be included in your code to show their use, and to confirm that your data structures hold expected values.
Hint: Test the data structures, not output to the screen, as unit testing console output is challenging
