Question

Congratulations! Your research team has just been awarded a $50M multi-
year project, jointly funded by DARPA, Google, and McDonald’s, to produce
DWIM: The first 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 it’s 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.

Well this is the textbook exercise, and there is nothing more, so it needs to be clear

Answer 1

Minimum edit distance to convert from one string to other:

CODE:

#include <bits/stdc++.h>
using namespace std;

int min(int x, int y, int z)
{
    return min(min(x, y), z);
}
int EditDistance(string W, string Y, int m, int n)
{
    // Create a table to store results of subproblems
    int dp[m + 1][n + 1];

    // Fill d[][] in bottom up manner
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            // If first string is empty, only option is to
            // insert all characters of second string
            if (i == 0)
                dp[i][j] = j; // Min. operations = j

            // If second string is empty, only option is to
            // remove all characters of second string
            else if (j == 0)
                dp[i][j] = i; // Min. operations = i

            // If last characters are same, ignore last char
            // and recur for remaining string
            else if (W[i - 1] == Y[j - 1])
                dp[i][j] = dp[i - 1][j - 1];

            // If the last character is different, consider all
            // possibilities and find the minimum
            else
                dp[i][j] = 1 + min(dp[i][j - 1], // Insert
                                   dp[i - 1][j], // Remove
                                   dp[i - 1][j - 1]); // Replace
        }
    }

    return dp[m][n];
}

int main()
{
    string W,Y;
    cin>>W>>Y;
    int result= EditDistance(W,Y,W.size(),Y.size());
    cout<<result;

    return 0;
}