Congratulations! Your research team has just been awarded a $50M multi- year project, jointly funded by DARPA, Google, and McDonalds, to produce DWIM: The rst compiler to read programmers minds! Your proposal and your numerous press releases all promise that DWIM will automatically correct errors in any given piece of code, while modifying that code as little as possible. Unfortunately, now its time to start actually making the thing work. As a warmup exercise, you decide to tackle the following necessary subproblem. Recall thatthe edit distance between two strings is the minimum number of single-character insertions, deletions, and replacements required to transform one string into the other. An arithmetic expression is a string w such that w is a string of one or more decimal digits, w = ( x ) for some arithmetic expression x , or w = x y for some arithmetic expressions x and y and some binary operator . Suppose you are given a string of tokens from the alphabet { # ,, ( , ) } , where # represents a decimal digit and represents a binary operator. Describe and analyze an algorithm to compute the minimum edit distance from the given string to an arithmetic expression.

this is the whole task, not known can therefore not possible