---
tilte: program III
---
> 放在這裡厲害了[name=Joe][color=#FF0000]
>
# Program III
## <i class="fa fa-user">ZoneTwelve</i>
```C++=
#define INT_MAX 2147483647
#define INT_MIN -2147483647 - 1
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
using namespace std;
stringstream ss;
class slice{
public:
char o;
int a, b, c, d, k;
void apply(int A, int B, int C, int D){a=A;b=B;c=C;d=D;}
void print(){cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<k<<"\n";}
}minPath[999][999], maxPath[999][999];
int len;
int eval(int a, char op, int b) {
switch(op){case '*':return a*b;case '+':return a+b;case '-':return a-b;}
return 0;
}
int ups[999], dws[999];
void dfs(int y, int x, int c){
if(x==y)return;
slice path = c==1?maxPath[y][x]:minPath[y][x];
if(y!=0)ups[y]++;
if(x!=len&&y!=0)dws[x]++;
switch(path.o){
case 'a':
dfs(y, path.k, 0);
dfs(path.k+1, x, 0);
break;
case 'b':
dfs(y, path.k, 0);
dfs(path.k+1, x, 1);
break;
case 'c':
dfs(y, path.k, 1);
dfs(path.k+1, x, 0);
break;
case 'd':
dfs(y, path.k, 1);
dfs(path.k+1, x, 1);
break;
}
}
int solution(vector<int> num, vector<char> sym) {
len = num.size();
int minVal[len][len];
int maxVal[len][len];
for(int i = 0; i < len; i++){
for(int j = 0; j < len; j++){
minVal[i][j] = 999; // easy debug
maxVal[i][j] = -999;
minPath[i][j].o = -1;
maxPath[i][j].o = -1;
if(i == j){
minVal[i][j] = num[i];
maxVal[i][j] = num[i];
}
}
}
for (int s = 0; s < len - 1; s++){
for (int i = 0; i < len - s - 1; i++){
int j = i + s + 1;
int minval = INT_MAX;
int maxval = INT_MIN;
int chV = INT_MIN;
int chI = -1;
int maxK = INT_MIN, minK = INT_MAX;
for (int k = i; k < j; k++ ){
int a = eval(minVal[i][k], sym[k], minVal[k + 1][j]); // like javascript eval(`${num}${op}${num}`);
int b = eval(minVal[i][k], sym[k], maxVal[k + 1][j]);
int c = eval(maxVal[i][k], sym[k], minVal[k + 1][j]);
int d = eval(maxVal[i][k], sym[k], maxVal[k + 1][j]);
//minPath[i][j].o = choose(0, a, b, c, d);
//maxPath[i][j].o = choose(1, a, b, c, d);
minPath[i][j].apply(minVal[i][k], minVal[k + 1][j], maxVal[i][k], maxVal[k + 1][j]);
maxPath[i][j].apply(minVal[i][k], minVal[k + 1][j], maxVal[i][k], maxVal[k + 1][j]);
minval = min(minval,min(a,min(b,min(c,d))));
maxval = max(maxval,max(a,max(b,max(c,d))));
if(maxval==a)maxPath[i][j].o = 'a';
if(maxval==b)maxPath[i][j].o = 'b';
if(maxval==c)maxPath[i][j].o = 'c';
if(maxval==d)maxPath[i][j].o = 'd';
if(minval==a)minPath[i][j].o = 'a';
if(minval==b)minPath[i][j].o = 'b';
if(minval==c)minPath[i][j].o = 'c';
if(minval==d)minPath[i][j].o = 'd';
if(maxK<maxval){
maxPath[i][j].k = k;
maxK = maxval;
}
if(minK>minval){
minPath[i][j].k = k;
minK = minval;
}
}
minVal[i][j] = minval;
maxVal[i][j] = maxval;
}
}
for(int i=0;i<len;i++){
}
dfs(0, len-1, 1);
for(int i=0;i<len;i++){
for(int b=0;b<ups[i];b++)
cout << '(';
// cout << '(';
cout << num[i] ;
// cout << ')';
for(int b=0;b<dws[i];b++)
cout << ')';
if(i+1<len)
cout << sym[i];
}
//cout << " = " << maxVal[0][len - 1] << endl; // return maxVal[0][len - 1];
}
int main(){
int n;
char s;
string tmp;
cin>>tmp;
vector<int> num;
vector<char> sym;
ss<<tmp;
ss>>n;
num.push_back(n);
for(int i=0;i<3;i++)if(incase[i]==tmp)testcase=i;
while(!ss.eof()){
ss>>s;
sym.push_back(s);
ss>>n;
num.push_back(n);
}
ss.clear();
solution(num, sym);
}
```
# @jerrymark611
``` pseudo=
#include <iostream>
#include <vector>
#include <sstream>
#include <climits>
using namespace std;
enum situation {MAX_MAX, MAX_MIN, MIN_MIN, MIN_MAX};
struct record{
int MAX ;
int MIN ;
situation MAX_case;
situation MIN_case;
};
record calculate( vector<int>number, vector<char>symbol, vector<vector<int>>Max, vector<vector<int>>Min, int l, int k, int r){
//calculate the value from l th to r th numbers' operation
int a_MAX, a_MIN, b_MAX, b_MIN, MAX = INT_MIN, MIN = INT_MAX;
situation MAX_stem, MIN_stem;
//first operand
if(l==k){
a_MAX = number[l];
a_MIN = number[l];
}
else
{
a_MAX = Max[l][k];
a_MIN = Min[l][k];
}
//second operand
if(k+1==r)
{
b_MAX = number[r];
b_MIN = number[r];
}
else
{
b_MAX = Max[k+1][r];
b_MIN = Min[k+1][r];
}
switch (symbol[k]){
case '+': {
if(a_MAX+b_MAX>MAX){
MAX = a_MAX+b_MAX;
MAX_stem = MAX_MAX;
}
if(a_MAX+b_MIN>MAX){
MAX = a_MAX+b_MIN;
MAX_stem = MAX_MIN;
}
if(a_MIN+b_MIN>MAX){
MAX = a_MIN+b_MIN;
MAX_stem = MIN_MIN;
}
if(a_MIN+b_MAX>MAX){
MAX = a_MIN+b_MAX;
MAX_stem = MIN_MAX;
}
if(a_MAX+b_MAX<MIN){
MIN = a_MAX+b_MAX;
MIN_stem = MAX_MAX;
}
if(a_MAX+b_MIN<MIN){
MIN = a_MAX+b_MIN;
MIN_stem = MAX_MIN;
}
if(a_MIN+b_MIN<MIN){
MIN = a_MIN+b_MIN;
MIN_stem = MIN_MIN;
}
if(a_MIN+b_MAX<MIN){
MIN = a_MIN+b_MAX;
MIN_stem = MIN_MAX;
}
return record{MAX, MIN, MAX_stem, MIN_stem};
case '-': {
if(a_MAX-b_MAX>MAX){
MAX = a_MAX-b_MAX;
MAX_stem = MAX_MAX;
}
if(a_MAX-b_MIN>MAX){
MAX = a_MAX-b_MIN;
MAX_stem = MAX_MIN;
}
if(a_MIN-b_MIN>MAX){
MAX = a_MIN-b_MIN;
MAX_stem = MIN_MIN;
}
if(a_MIN-b_MAX>MAX){
MAX = a_MIN-b_MAX;
MAX_stem = MIN_MAX;
}
if(a_MAX-b_MAX<MIN){
MIN = a_MAX-b_MAX;
MIN_stem = MAX_MAX;
}
if(a_MAX-b_MIN<MIN){
MIN = a_MAX-b_MIN;
MIN_stem = MAX_MIN;
}
if(a_MIN-b_MIN<MIN){
MIN = a_MIN-b_MIN;
MIN_stem = MIN_MIN;
}
if(a_MIN-b_MAX<MIN){
MIN = a_MIN-b_MAX;
MIN_stem = MIN_MAX;
}
return record{MAX, MIN, MAX_stem, MIN_stem};
}
case '*': {
//MAX = a_MAX * b_MAX;
if(a_MAX*b_MAX>MAX){
MAX = a_MAX*b_MAX;
MAX_stem = MAX_MAX;
}
if(a_MAX*b_MIN>MAX){
MAX = a_MAX*b_MIN;
MAX_stem = MAX_MIN;
}
if(a_MIN*b_MIN>MAX){
MAX = a_MIN*b_MIN;
MAX_stem = MIN_MIN;
}
if(a_MIN*b_MAX>MAX){
MAX = a_MIN*b_MAX;
MAX_stem = MIN_MAX;
}
if(a_MAX*b_MAX<MIN){
MIN = a_MAX*b_MAX;
MIN_stem = MAX_MAX;
}
if(a_MAX*b_MIN<MIN){
MIN = a_MAX*b_MIN;
MIN_stem = MAX_MIN;
}
if(a_MIN*b_MIN<MIN){
MIN = a_MIN*b_MIN;
MIN_stem = MIN_MIN;
}
if(a_MIN*b_MAX<MIN){
MIN = a_MIN*b_MAX;
MIN_stem = MIN_MAX;
}
return record{MAX, MIN, MAX_stem, MIN_stem};}
}
default: exit(1);
}
}
void printSolution(vector<int> number, vector<char> symbol, vector<vector<int>> s, vector<vector<int>> Max, vector<vector<int>> Min, vector<vector<int>> leftMax, vector<vector<int>>rightMax, int l, int r, bool isMax, bool first){
int a,b;
bool aMax, bMax;
if(l==r)
{
cout<<number[l];
return;
}
int k ;
if(isMax)
{
k = s[l][r];
if (leftMax[l][r]) // max get from left max operand
{ //a = Max[l][k];
aMax = true;
}
else
{ //a = Min[l][k]; // max get by left min operand
aMax = false;
}
if (rightMax[l][r])
{ //b = Max[k+1][r];
bMax = true;
}
else
{ //b = Min[k+1][r];
bMax = false;
}
}
else
{
k = s[r][l];
if (leftMax[r][l]) // min get from left max operand
{ //a = Max[l][k];
aMax = true;
}
else
{ //a = Min[l][k]; // min get by left min operand
aMax = false;
}
if (rightMax[r][l])
{ //b = Max[l][k+1];
bMax = true;
}
else
{ //b = Min[l][k+1];
bMax = false;
}
}
if(!first)
cout << '(';
if(aMax)
printSolution(number, symbol, s, Max, Min, leftMax, rightMax, l, k, 1, 0);
else
printSolution(number, symbol, s, Max, Min, leftMax, rightMax, l, k, 0, 0);
//if(isMax)
cout << symbol[k];
//else
// cout<<symbol[s[r][l]];
if(bMax)
printSolution(number, symbol, s, Max, Min, leftMax, rightMax, k+1, r, 1, 0);
else
printSolution(number, symbol, s, Max, Min, leftMax, rightMax, k+1, r , 0, 0);
if(!first)
cout << ')';
return ;
}
//number[0..n-1], m[0..n-1][0..n-1], s[0..n-2][1..n-1]
void maxvalue(vector<int> number, vector<char> symbol){
//m(number.size(), vector<int> (number.size(), 0)),
vector<vector<int>> s(number.size(), vector<int> (number.size(), 0)); //position to cut
vector<vector<int>> leftMax(number.size(), vector<int> (number.size(), 0)), rightMax(number.size(), vector<int> (number.size(), 0)); // choose max?
vector<vector<int>> Max(number.size(), vector<int> (number.size(), INT_MIN)), Min(number.size(), vector<int> (number.size(), INT_MAX)); //values
int max, min;
record temp;
for (int i=0 ;i< number.size();i++)
for (int j=0 ;j< number.size();j++)
if(i==j)
{
Max[i][j] = number[i];
Min[i][j] = number[i];
s[i][j] = -1;
}
if(number.size()==1){
cout<<'('<<number[0]<<") = "<<number[0];
return;
}
//length
for(int l = 1;l < number.size();l++){
//left and right, jth to j + i - 1th number
for(int i=0, j=l; i<number.size() && j<number.size(); i++, j++){
//the maximum of calcutlation of i numbers
for(int k = i;k < j ;k++) //search the best location separate the formula
{
temp = calculate(number, symbol,Max, Min, i, k, j); //return a record of max and min
if( Max[i][j] < temp.MAX)
{
Max[i][j] = temp.MAX;
s[i][j] = k;
if(temp.MAX_case==MAX_MAX)
{
leftMax [i][j] =1;
rightMax [i][j] =1;
}
else if(temp.MAX_case==MAX_MIN)
{
leftMax [i][j] =1;
rightMax [i][j] =0;
}
else if(temp.MAX_case==MIN_MAX)
{
leftMax [i][j] =0;
rightMax [i][j] =1;
}
else
{
leftMax [i][j] =0;
rightMax [i][j] =0;
}
}
if(Min[i][j]> temp.MIN)
{
Min[i][j] = temp.MIN;
s[j][i] = k;
if(temp.MIN_case==MAX_MAX)
{
leftMax [j][i] =1;
rightMax [j][i] =1;
}
else if(temp.MIN_case==MAX_MIN)
{
leftMax [j][i] =1;
rightMax [j][i] =0;
}
else if(temp.MIN_case==MIN_MAX)
{
leftMax [j][i] =0;
rightMax [j][i] =1;
}
else
{
leftMax [j][i] =0;
rightMax [j][i] =0;
}
}
}
}
}
printSolution(number, symbol, s, Max, Min, leftMax, rightMax, 0, number.size()-1, 1, 1);
cout<<" = "<<Max[0][number.size()-1];
}
int main(){
string exp;
cin>>exp;
stringstream ss;
ss<<exp;
int i =0;
char h;
vector<int> number;
vector<char> symbol;
while(ss>>i){
number.push_back(i);
ss>>h;
symbol.push_back(h);
}
maxvalue(number, symbol);
}
```
# program III
## topic
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 ‘*’.
Input: expression Ex: 2+7 * 5-3 * 6
Output: (((2+7)*5)-3)*6 or ((((2+7)*5)-3)*6)
1 <= expression's length <= 30
if there are several solutions, output one of them.
## Solution
Time complexity: $O(n^3)$
//for there are triple nested for-loops
using vector
the outter loop: length of number
the middle loop: start of index
```
Pseudocode
calculate(number, sign, m, l, k, r)
//number is an array of number, sign is an array of char [0 : n-1]
//m is a 2-dimension array [0:n-1][0:n-1]
//l is left bound index, r is right bound index
//k is the index of the position to separate
int a,b
if l==k do
a = number[l]
else
a = m[l][k]
end if
if k+1 == r d0
b = number[r]
else
b = m[k+1][r]
end if
if sign[k] == '+' do
return a+b
else if sign[k]=='-' do
return a-b
else if sign[k]== '*' do
return a*b
end if
printSolution(number, sign, s, int i, int j){
//s is a 2-dimension array of solution [0:n-1][0:n-1]
if i == j do
print (number[i]);
return
end if
print('(')
printSolution(number, sign, s, i, s[i][j]);
print(sign[s[i][j]])
printSolution(number, sign, s, s[i][j] + 1, j)
print(')')
}
//number[0..n-1], m[0..n-1][0..n-1], s[0..n-2][1..n-1]
maxvalue(number, sign){
number[0..n-1], sign[0..n-1][0..n-1], m[0..n-1][0..n-1], s[0..n-2][1..n-1]
int i, j, k, max, num;
//the length of numbers
for i from 2 to number.size() do //O(n)
//left and right, jth to j + i - 1th number
for j from 0 to number.length()-i do //O(n)
max = INT_MIN
//the maximum of calcutlation of i numbers
for k from j to i+j-2 do //O(n)
num = calculate(number, sign, m, j, k, i+j-1)
if max < num do
max = num
s[j][i + j - 1] = k
end if
end for
m[j][i + j - 1] = max
end for
end for
printSolution(number, sign, s, 0, number.size() - 1)
print('='m[0][number.size() - 1])
}
```
```c++=
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int calculate( vector<int>number, vector<char>sign, vector<vector<int>> m, int l, int k, int r){
int a,b;
if(l==k)
a = number[l];
else
a = m[l][k];
if(k+1==r)
b = number[r];
else
b = m[k+1][r];
switch (sign[k]){
case '+': return a+b;
case '-': return a-b;
case '*': return a*b;
default: exit(1);
}
}
void printSolution(vector<int> number, vector<char> sign, vector<vector<int>> s, int i, int j){
if(i == j){
cout << number[i];
return;
}
cout << '(';
printSolution(number, sign, s, i, s[i][j]);
cout << sign[s[i][j]];
printSolution(number, sign, s, s[i][j] + 1, j);
cout << ')';
}
//number[0..n-1], m[0..n-1][0..n-1], s[0..n-2][1..n-1]
void maxvalue(vector<int> number, vector<char> sign){
vector<vector<int>> m(number.size(), vector<int> (number.size(), 0)), s(number.size(), vector<int> (number.size(), 0));
int i, j, k, max, num;
//the length of numbers
for(i = 2;i <= number.size();i++){
//left and right, jth to j + i - 1th number
for(j = 0;j + i - 1 < number.size();j++){
max = INT_MIN;
//the maximum of calcutlation of i numbers
for(k = j;k < i + j - 1;k++){
num = calculate(number, sign, m, j, k, i+j-1);
if(max < num){
max = num;
s[j][i + j - 1] = k;
}
}
m[j][i + j - 1] = max;
}
}
printSolution(number, sign, s, 0, number.size() - 1);
cout << " = " << m[0][number.size() - 1] << endl;
}
int main(){
vector<int> number;
vector<char> sign;
int n, number_length;
char c;
cout << "number of operands:";
cin>>number_length;
cout << "expression:";
while(number_length--){
cin>>n;
number.push_back(n);
if(number_length!=0){
cin>>c;
sign.push_back(c);
}
}
maxvalue(number, sign);
}
```
Test case:
(1) Input: 5-8+7*4-8+9 ; Output: 5-((8+7)*(4-(8+9)))
(2) Input: -11+22--11-22 ; Output: -11+(22-(-11-22))
(3) Input: 2-7*5+1-4+8*3 ; Output: 2-(7*(5+(1-((4+8)*3))))
Sign in with Wallet
Connect another wallet