表达式加括号使和最大

Give you a expression,you can add some parenthesis to maximize result.Example as following:
1 + 2 * 3 - 2
Its result is 7 in the example.But you can add a parenthesis like (1 + 2) * 3 - 2,then
the result is 7,and so it is the maximization of the example.You job is to find the maximization of a expression.
To simplify this problem,you can assume that expression contains only operator +, * and -, integers is none negative

觉得这题还是出的很好的，没人回答我晚上贴答案了哈

应为有负数的存在，一开始还以为是NP复杂，没想到DP可以记录最大值，同时一样可以记录最小值。对于加号来说，两边最大和最大，两边最小和最小。对于乘来说，两边最大最小的4种组合求乘积的最大最小值...

1. 
   
2. struct OPERATION
   
3. {
   
4.         char cOpr;
   
5.         int nLft;
   
6.         int nRgt;
   
7. 
   
8.         OPERATION(int l = 0, int r = 0, char op = 0)
   
9.         {
   
10.                 nLft = l;
    
11.                 nRgt = r;
    
12.                 cOpr = op;
    
13.         }
    
14. };
    
15. 
    
16. int GetNoneNegNum(const char*& pIter)
    
17. {
    
18.         int nRet = -1;
    
19.         while (*pIter == ' ') pIter++;
    
20. 
    
21.         while (*pIter >= '0' && *pIter <= '9')
    
22.         {
    
23.                 if (nRet < 0) nRet = 0;
    
24.                 nRet = nRet*10 + *pIter - '0';
    
25.                 pIter++;
    
26.         }
    
27. 
    
28.         return nRet;
    
29. }
    
30. 
    
31. char GetOperator(const char*& pIter)
    
32. {
    
33.         while (*pIter == ' ') pIter++;
    
34. 
    
35.         if (*pIter != '-' && *pIter != '+' && *pIter != '*')
    
36.                 return 0;
    
37.        
    
38.         char cRet = *pIter++;
    
39.         return cRet;
    
40. }
    
41. 
    
42. bool Parse(const char* szString, vector<OPERATION>& vec, int nLft)
    
43. {
    
44.         if (NULL == szString) return false;
    
45. 
    
46.         if (vec.empty())
    
47.                 nLft = GetNoneNegNum(szString);
    
48.         if (nLft < 0) return false;
    
49. 
    
50.         while (*szString == ' ') szString++;
    
51.         if ('\0' == *szString) return true;
    
52. 
    
53.         int cOpr = GetOperator(szString);
    
54.         if (0 == cOpr) return false;
    
55. 
    
56.         int nRgt = GetNoneNegNum(szString);
    
57.         if (nRgt < 0) return false;
    
58. 
    
59.         vec.push_back(OPERATION(nLft, nRgt, cOpr));
    
60. 
    
61.         return Parse(szString, vec, nRgt);
    
62. }
    
63. 
    
64. int Calc(int l, char cOpr, int r)
    
65. {
    
66.         if ('+' == cOpr) return l+r;
    
67.         if ('-' == cOpr) return l-r;
    
68.         if ('*' == cOpr) return l*r;
    
69.         return 0;
    
70. }
    
71. 
    
72. bool GetMaxResult(const char* szString, int& res)
    
73. {
    
74.         vector<OPERATION> recs;
    
75.         if (!Parse(szString, recs, 0))
    
76.                 return false;
    
77. 
    
78.         struct RECORD
    
79.         {
    
80.                 int nMax;
    
81.                 int nMin;
    
82.         };
    
83. 
    
84.         int nSize = recs.size();
    
85.         RECORD** pRec = new RECORD*[nSize];
    
86.         for (int i = 0; i < nSize; i++)
    
87.                 pRec[i] = new RECORD[nSize];
    
88. 
    
89.         for (int i = 0; i < nSize; i++)
    
90.                 pRec[i][i].nMax = pRec[i][i].nMin = Calc(recs[i].nLft, recs[i].cOpr, recs[i].nRgt);
    
91. 
    
92.         for (int i = 1; i < nSize; i++)
    
93.                 for (int j = 0; j + i < nSize; j++)
    
94.                 {
    
95.                         int nMax = 0;
    
96.                         int nMin = 0;
    
97. 
    
98.                         for (int k = 0; k <= i; k++)
    
99.                         {
    
100.                                 int nLMax, nLMin, nRMax, nRMin;
     
101.                                 if (0 == k)
     
102.                                         nLMin = nLMax = recs[j].nLft;
     
103.                                 else
     
104.                                 {
     
105.                                         nLMax = pRec[j][j+k-1].nMax;
     
106.                                         nLMin = pRec[j][j+k-1].nMin;
     
107.                                 }
     
108. 
     
109.                                 if (i == k)
     
110.                                         nRMin = nRMax = recs[j+i].nRgt;
     
111.                                 else
     
112.                                 {
     
113.                                         nRMax = pRec[j+k+1][j+i].nMax;
     
114.                                         nRMin = pRec[j+k+1][j+i].nMin;
     
115.                                 }
     
116. 
     
117.                                 int nTmpMax = 0;
     
118.                                 int nTmpMin = 0;
     
119.                                 char cOp = recs[j+k].cOpr;
     
120. 
     
121.                                 if ('+' == cOp)
     
122.                                 {
     
123.                                         nTmpMax = nLMax + nRMax;
     
124.                                         nTmpMin = nLMin + nRMin;
     
125.                                 }
     
126. 
     
127.                                 if ('-' == cOp)
     
128.                                 {
     
129.                                         nTmpMax = nLMax - nRMin;
     
130.                                         nTmpMin = nRMin + nLMax;
     
131.                                 }
     
132. 
     
133.                                 if ('*' == cOp)
     
134.                                 {
     
135.                                         nTmpMax = max(max(nLMax*nRMax, nLMax*nRMin), max(nLMin*nRMin, nLMin*nRMax));
     
136.                                         nTmpMin = min(min(nLMax*nRMax, nLMax*nRMin), min(nLMin*nRMin, nLMin*nRMax));
     
137.                                 }
     
138. 
     
139.                                 nMax = nMax > nTmpMax ? nMax : nTmpMax;
     
140.                                 nMin = nMin < nTmpMin ? nMin : nTmpMin;
     
141.                         }
     
142. 
     
143.                         pRec[j][j+i].nMax = nMax;
     
144.                         pRec[j][j+i].nMin = nMin;
     
145.                 }
     
146. 
     
147.         res = pRec[0][nSize-1].nMax;
     
148.         for (int i = 0; i < nSize; i++)
     
149.                 delete []pRec[i];
     
150.         delete []pRec;
     
151. 
     
152.         return true;
     
153. }
     
154. 
     

复制代码

思路是可以用DP,对每个字组合记录最大结果和最小结果
对于(...)(+/-/*)(...)来说，
+ : 最大的结果取两边最大值相加，最小的结果为两边最小值相加
- :  最大的结果为左边最大值减去右边最小值， 最小的结果相反
* : 最大最小的结果为[minL*minR, minL*LargR, LargL*minL, LargL*minR]的最大，最小值