補考 10

HW4-5

【題目】

【題目】

A mathematical expression is given without parentheses. Design an algorithm to parenthesize the expression such that the value of the expression is maximized. For example, consider the expression: 2+7⋅5. There are two ways to parenthesize the expression 2+(7⋅5) = 37 and (2+7)⋅5 = 45, so in this case, your algorithm should output the second expression. Here, you may assume the given expressions contain only 3 kinds of binary operators ‘+’, ‘−’, and ‘⋅’.

【解題思路】

因為題目說有 + - * 三種運算符號，因此需要考慮 負值x負值 之類的狀況，所以要探討每個區間最大最小值做運算的狀況(有可能會是兩個子區間的最小值相乘而得到最大值)，首先我們可以將表達式

$a_{1}o{p}_1{a}_{2}o{p}_2\cdots o{p}_{n-1}{a}_n$的數字

$[a_1,a_2,\cdots ,a_n]$ 和運算符號

$[o{p}_1,o{p}_2,\cdots ,o{p}_{n-1}]$ 分開來看。

而我們需要有兩個二維矩陣(數字大小)分別儲存子表達式內最大值max[i][j]及最小值min[i][j]，代表 i 到 j 所計算出來的最大值及最小值，而運算符號則放在一維陣列內 op[n-1]。

【遞迴式】

assume amount of input is n

$1\le i,j\le n$

$max[i][j],min[i][j]=a_i,ifi=j.$

$$\begin{array}{r}max[i][j]=Ma{x}_{i\le k<j}\{\begin{array}{ll}max[i][k]& op[k]max[k+1][j]\\ max[i][k]& op[k]min[k+1][j]\\ min[i][k]& op[k]max[k+1][j]\\ min[i][k]& op[k]min[k+1][j]\end{array}，max[i][j]\mathrm{代}\mathrm{表}subexpression\mathrm{數}\mathrm{字}i\mathrm{到}j\mathrm{裡}\mathrm{所}\mathrm{算}\mathrm{出}\mathrm{來}\mathrm{的}\mathrm{最}\mathrm{大}\mathrm{值}，\mathrm{運}\mathrm{算}\mathrm{式}\mathrm{的}Maximum\mathrm{在}max[1][n]\end{array}$$

$$\begin{array}{r}min[i][j]=Mi{n}_{i\le k<j}\{\begin{array}{ll}max[i][k]& op[k]max[k+1][j]\\ max[i][k]& op[k]min[k+1][j]\\ min[i][k]& op[k]max[k+1][j]\\ min[i][k]& op[k]min[k+1][j]\end{array}，min[i][j]\mathrm{代}\mathrm{表}subexpression\mathrm{數}\mathrm{字}i\mathrm{到}j\mathrm{裡}\mathrm{所}\mathrm{算}\mathrm{出}\mathrm{來}\mathrm{的}\mathrm{最}\mathrm{小}\mathrm{值}，\mathrm{運}\mathrm{算}\mathrm{式}\mathrm{的}Minimum\mathrm{在}min[1][n]\end{array}$$

【蘇都扣】

//初始值設定 
n = num_size;
for i from 1 to n:
    max[i][i] = a[i],  min[i][i] = a[i];

//主要部份
get_Max_expression(1,n){
    for q from 1 to n-1:    //不能超過n，固定現在運算的長度。
        for i from 1 to n-q:   //會是以陣列為斜的算下去
            j = i + q;
            (max[i][j],min[i][j]) = sub_expression_result(i, j);
    return max[1][n];
}

//跑遞迴式
sub_expression_result(i, j){
    minimum = INT_MAX, maximum = INT_MIN;
    for k from i to j-1:
        MM = max[i][k] op[k] max[k+1][j];    //op是運算符號
        Mm = max[i][k] op[k] min[k+1][j];
        mM = min[i][k] op[k] max[k+1][j];
        mm = min[i][k] op[k] min[k+1][j];
        maximum = Max(MM, Mm, mM, mm, maximum);
        minimum = Min(MM, Mm, mM, mm, minimum);
    return maximum, minimum;
}

【Example Expression = 3 - 4 * 7 + 6】

min	1	2	3	4
1	3	-1	-25	-49
2		-4	-28	-52
3			7	13
4				6

max	1	2	3	4
1	3	-1	-7	-1
2		-4	-28	-22
3			7	13
4				6

$Ans:max[1][4]=-1_{\mathrm{\#}}$

【括號】

//主要部份
//maxExp[][], minExp[][] 是用來記錄發生 max, min 時的 expression
get_Max_expression(1,n){
    for q from 1 to n-1:    //不能超過n，固定現在運算的長度。
        for i from 1 to n-q:   //會是以陣列為斜的算下去
            j = i + q;
            (max[i][j],min[i][j],MT,mT,MF,mF) = sub_expression_result(i, j);
            placing_paretheses(maxExp,MT,MF,i,j);
            placing_paretheses(minExp,mT,mF,i,j);
    return max[1][n], maxExp[1][n];
}

//跑遞迴式
//MT, mT 用來記錄當 max, min 發生, k 的值 
//MF, mF 用來記錄當 max, min 發生, 是種組合
sub_expression_result(i, j){
    minimum = INT_MAX, maximum = INT_MIN;
    for k from i to j-1:
        MM = max[i][k] op[k] max[k+1][j];    //op是運算符號
        Mm = max[i][k] op[k] min[k+1][j];
        mM = min[i][k] op[k] max[k+1][j];
        mm = min[i][k] op[k] min[k+1][j];
        maxTemp = Max(MM, Mm, mM, mm);
        minTemp = Min(MM, Mm, mM, mm);
        if maxTemp > maximum // 表 maxTemp 為當前最大
            maximum = maxTemp;
            MT = k;
            MF is the the combination about maximum; //MM, mm, Mm?
        if minTemp < minimum // 表 minTemp 為當前最小
            minimum = minTemp;
            mT = k;
            mF is the the combination about minimum;
    return maximum, minimum, MT, mT, MF, mF;
}

//插入括號
placing_paretheses(Exp[][], T, Flag, i, j){
    switch(Flag)
    {
        case 'MM':
            exp[i][j] = '(' + maxExp[i][T] + op[T] + maxExp[T + 1][j] + ')';
            break;
        case 'Mm':
            exp[i][j] = '(' + maxExp[i][T] + op[T] + minExp[T + 1][j] + ')';
            break;
        case 'mM':
            exp[i][j] = '(' + minExp[i][T] + op[T] + maxExp[T + 1][j] + ')';
            break;
        case 'mm':
            exp[i][j] = '(' + minExp[i][T] + op[T] + minExp[T + 1][j] + ')';
            break;
    }
}

【Example Expression = 3 - 4 * 7 + 6】

max	1	2	3	4
1	3	(3-4)	((3-4)*7)	(((3-4)*7)+6)
2		-4	(4*7)	(4*(7+6))
3			7	(7+6)
4				6

min	1	2	3	4
1	3	(3-4)	(3-(4*7))	(3-(4*(7+6)))
2		-4	(4*7)	((4*7)+6)
3			7	(7+6)
4				6