Can you help me solve problem $1$ and $2$ by coding

Homework Overview

In string $(($I am balanced$))$ the parentheses are balanced, but in $($Not balanced$)$ they are not because a closing parenthesis is missing and so an opening parenthesis is unmatched. The modules in this assignment examine a string containing parentheses and report the number of unmatched closing, $),$ and opening, $(,$ parentheses. Both modules put these numbers on outputs left$\_$out$\_$n$\_$unmat$\_$close and right$\_$out$\_$n$\_$unmat$\_$open. The parentheses in a$($b$)$ c and $(()$a$)()$ are correctly matched. The parentheses in $()),((()),$ and $))(($ are not. For inputs like $(),(()),$ and $()()$ both outputs should be zero. For $)$ and $())$ the number of unmatched closing parentheses is one and so output left$\_$out$\_$n$\_$unmat$\_$close should be $1$ and output right$\_$out$\_$n$\_$unmat$\_$open should be $0.$ See the testbench output for more examples.

In both modules, pmatch$\_$base $($Problem $1)$ and pmatch$\_$mark $($Problem $2),$ the string appears on input str$.$ In pmatch$\_$mark there is an additional output, str$\_$marked, which should be set to a version of the string in which the correctly matched parentheses are replaced by angle brackets. For example, for input str$=\text{'}(()\text{'}$ the output shold be str$\_$marked See the testbench output for more examples.

The modules each have parameter n$.$ Input str and output str$\_$marked are n$-$element unpacked $($ordinary$)$ arrays of $4-$bit quantities. For convenience enumeration constants are defined for the characters used in this assignment:

$```$

typedef enum logic $[3$:$0]$

$\{$ Char$\_$Blank, Char$\_$Dot,

Char$\_$Open, Char$\_$Close,

Char$\_$Open$\_$Okay, Char$\_$Close$\_$Okay $\}$ Char;

$```$

The input str can consist of any of the first four values. There is no distinction between Char$\_$Blank and Char$\_$Dot, they are stand$-$ins for arbitrary characters and neither affects paren$-$

thesis matching. The last two, Char$\_$Open$\_$Okay and Char$\_$Close$\_$Okay are to be used in Problem $2$ for replacing properly matched parenthesis.

Those who are unsure of how to work with str or of just what the modules are supposed to do should examine modules pmatch$\_$comb$\_$base and pmatch$\_$comb$\_$mark. Module pmatch$\_$comb$\_$base will pass the testbench for Problem $1($if it were renamed pmatch$\_$base$)$ and pmatch$\_$comb$\_$mark would pass the testbench for Problem $2($if renamed$).$

These comb modules compute their results by scanning the string from left to right. In their synthesized hardware the critical path appears to be proportional to $\backslash ($ n $\backslash ),$ the string length. That's too long a critical path for our purposes. In Problems $1$ and $2$ this is to be overcome by using a recursive module structure that describes tree$-$like hardware. In a correct solution the critical path will be closer to $\backslash (\backslash$log n $\backslash ),$ and the cost will be lower too.

The synthesis output below shows the result of synthesizing the comb base module and a correct solution to Problem $1$ at exponentially increasing string lengths $\backslash (($n$=4,8,16,32)\backslash ).$ Notice that in the comb version the delay too increases exponentially $($in proportion to $\backslash ($ n $\backslash ))$ while the delay in the Problem $1$ solution increases more linearly. Absolute costs are lower too.

pmatch$\_$base$\_$n$4$

pmatch$\_$base$\_$n$8$

pmatch$\_$base$\_$n$16$

pmatch$\_$base$\_$n$32$

Testbench

To compile your code and run the testbench press F$9$ in an Emacs buffer in a properly set up

account. The testbench will apply inputs to several instantiations of modules pmatch$\_$base and

pmatch$\_$mark. The instantiations differ in the length of the string. At the end of execution the

number of errors for each module at each size are shown. The output below is from a correctly

solved assignment:

Total pmatch$\_$base n$=4$: Errors: $0$cl$,0$op$,0$mk$.$

Total pmatch$\_$base n$=5$: Errors: $0$cl$,0$op$,0$mk$.$

Total pmatch$\_$base n$=7$: Errors: $0$cl$,0$op$,0$mk$.$

Total pmatch$\_$base n$=8$: Errors: $0$cl$,0$op$,0$mk$.$

Total pmatch$\_$base n$=9$: Errors: $0$cl$,0$op$,0$mk$.$

Total pmatch$\_$base n$=17$: Errors: $0$cl$,0$op$,0$mk$.$

Total pmatch$\_$mark n$=4$: Errors: $0$cl$,0$op$,0$mk$.$

Total pmatch$\_$mark n$=5$: Errors: $0$cl$,0$op$,0$mk$.$

Total pmatch$\_$mark n$=7$: Errors: $0$cl$,0$op$,0$mk$.$

Total pmatch$\_$mark n$=8$: Errors: $0$cl$,0$op$,0$mk$.$

Total pmatch$\_$mark n$=9$: Errors: $0$cl$,0$op$,0$mk$.$

Total pmatch$\_$mark n$=17$: Errors: $0$cl$,0$op$,0$mk$.$

Each line starting with Total shows a tally of results. After Total the line shows the module name,

either pmatch$\_$base or pmatch$\_$mark, and n$,$ the length of the string. A tally of each output's error

is shown after Errors:, cl is the number of incorrect closing$-$parentheses values, op is the number

of opening$-$parenthesis values, and mk is the number of incorrectly marked strings.

Further up$,$ the testbench shows sample output and error details. For each instantiation the

first n$\_$errors$\_$show $=5$ incorrect outputs are shown on lines starting with Error. If it would

help to see more then feel free to search for n$\_$errors$\_$show and increase the value. In addition the

details of the first n$\_$samples$\_$show $=6$ correct outputs are shown on lines starting with Sample.

The output below shows correct outputs:

Starting pmat

The testbench starts applying patterns found

$5$