---
# System prepended metadata

title: Program III

---

---
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))))