Practical application $1$: Arithmetic operations.

$($a$)$ marks$]$ Design an algorithm that takes a string, which represents an arithmetic operation, as input and checks whether or not the brackets are correct $($balanced$)$ or incorrect $($unbalanced$).$ The input string may contain a combination of the following characters: $\{\},[],(),0,1,2,3,4,5,6,7,8,9,+,-,**\frac{,}{?}.$ An obvious hint for this algorithm is to use the stackbased solution discussed in class as a template, and hence you can use the stack implemented in #$1.$ Your algorithm must not check the correctness of the arithmetic operators$/$operands$,$ but only check for balanced brackets. Your algorithm should also show an error message when the string contains a character that is not one of those listed above. Provide the pseudocode of the algorithm.

$($b$)[3$ marks$]$ Implement the algorithm of $($a$)$ in your favorite programming language. Run the program in several cases, including the following $($more examples to be asked when the assignment is submitted$)$:

i$.,(9**[3**\{[\frac{3+3}{5}{]}^{**}7\}])$

iii.

ii$.\{2+[3-[\frac{4}{\frac{6}{9}}]]\}$

iv$.\{2-\frac{3^{**}\{\frac{6}{\left[\begin{array}{c}((9-0))\end{array}\right]}\}}{7}\}$

$($c$)[2$ marks$]$ Consider an input string of size $n$ : $($i$)$ what is the worst$-$case time that your algorithm takes to decide whether or not the string is correct $($balanced$)$ or incorrect $($unbalanced$)?($ii$)$ Why? Give your answers in terms of the O$-$notation.