Dada una expresión que contiene números y dos operadores ‘+’ y ‘*’, necesitamos encontrar el valor máximo y mínimo que se puede obtener evaluando esta expresión con diferentes paréntesis.
Ejemplos:
Input : expr = “1+2*3+4*5” Output : Minimum Value = 27, Maximum Value = 105 Explanation: Minimum evaluated value = 1 + (2*3) + (4*5) = 27 Maximum evaluated value = (1 + 2)*(3 + 4)*5 = 105
Podemos resolver este problema mediante el método de programación dinámica, podemos ver que este problema es similar a la multiplicación de strings de arrays , aquí estamos probando diferentes paréntesis para maximizar y minimizar el valor de expresión en lugar del número de multiplicación de arrays.
En el código a continuación, primero hemos separado los operadores y los números de la expresión dada, luego se toman dos arrays 2D para almacenar el resultado intermedio que se actualizan de manera similar a la multiplicación de strings de arrays y se prueban diferentes paréntesis entre los números, pero de acuerdo con los operadores que ocurren entre ellos. Al final, la última celda de la primera fila almacenará el resultado final en ambas arrays 2D.
CPP
// C++ program to get maximum and minimum
// values of an expression
#include <bits/stdc++.h>
using namespace std;
// Utility method to check whether a character
// is operator or not
bool isOperator(char op)
{
return (op == '+' || op == '*');
}
// method prints minimum and maximum value
// obtainable from an expression
void printMinAndMaxValueOfExp(string exp)
{
vector<int> num;
vector<char> opr;
string tmp = "";
// store operator and numbers in different vectors
for (int i = 0; i < exp.length(); i++)
{
if (isOperator(exp[i]))
{
opr.push_back(exp[i]);
num.push_back(atoi(tmp.c_str()));
tmp = "";
}
else
{
tmp += exp[i];
}
}
// storing last number in vector
num.push_back(atoi(tmp.c_str()));
int len = num.size();
int minVal[len][len];
int maxVal[len][len];
// initializing minval and maxval 2D array
for (int i = 0; i < len; i++)
{
for (int j = 0; j < len; j++)
{
minVal[i][j] = INT_MAX;
maxVal[i][j] = 0;
// initializing main diagonal by num values
if (i == j)
minVal[i][j] = maxVal[i][j] = num[i];
}
}
// looping similar to matrix chain multiplication
// and updating both 2D arrays
for (int L = 2; L <= len; L++)
{
for (int i = 0; i < len - L + 1; i++)
{
int j = i + L - 1;
for (int k = i; k < j; k++)
{
int minTmp = 0, maxTmp = 0;
// if current operator is '+', updating tmp
// variable by addition
if(opr[k] == '+')
{
minTmp = minVal[i][k] + minVal[k + 1][j];
maxTmp = maxVal[i][k] + maxVal[k + 1][j];
}
// if current operator is '*', updating tmp
// variable by multiplication
else if(opr[k] == '*')
{
minTmp = minVal[i][k] * minVal[k + 1][j];
maxTmp = maxVal[i][k] * maxVal[k + 1][j];
}
// updating array values by tmp variables
if (minTmp < minVal[i][j])
minVal[i][j] = minTmp;
if (maxTmp > maxVal[i][j])
maxVal[i][j] = maxTmp;
}
}
}
// last element of first row will store the result
cout << "Minimum value : " << minVal[0][len - 1]
<< ", Maximum value : " << maxVal[0][len - 1];
}
// Driver code to test above methods
int main()
{
string expression = "1+2*3+4*5";
printMinAndMaxValueOfExp(expression);
return 0;
}
Java
// Java program to get maximum and minimum
// values of an expression
import java.io.*;
import java.util.*;
class GFG
{
// Utility method to check whether a character
// is operator or not
static boolean isOperator(char op)
{
return (op == '+' || op == '*');
}
// method prints minimum and maximum value
// obtainable from an expression
static void printMinAndMaxValueOfExp(String exp)
{
Vector<Integer> num = new Vector<Integer>();
Vector<Character> opr = new Vector<Character>();
String tmp = "";
// store operator and numbers in different vectors
for (int i = 0; i < exp.length(); i++)
{
if (isOperator(exp.charAt(i)))
{
opr.add(exp.charAt(i));
num.add(Integer.parseInt(tmp));
tmp = "";
}
else
{
tmp += exp.charAt(i);
}
}
// storing last number in vector
num.add(Integer.parseInt(tmp));
int len = num.size();
int[][] minVal = new int[len][len];
int[][] maxVal = new int[len][len];
// initializing minval and maxval 2D array
for (int i = 0; i < len; i++)
{
for (int j = 0; j < len; j++)
{
minVal[i][j] = Integer.MAX_VALUE;
maxVal[i][j] = 0;
// initializing main diagonal by num values
if (i == j)
minVal[i][j] = maxVal[i][j]
= num.get(i);
}
}
// looping similar to matrix chain multiplication
// and updating both 2D arrays
for (int L = 2; L <= len; L++)
{
for (int i = 0; i < len - L + 1; i++)
{
int j = i + L - 1;
for (int k = i; k < j; k++)
{
int minTmp = 0, maxTmp = 0;
// if current operator is '+', updating
// tmp variable by addition
if (opr.get(k) == '+')
{
minTmp = minVal[i][k]
+ minVal[k + 1][j];
maxTmp = maxVal[i][k]
+ maxVal[k + 1][j];
}
// if current operator is '*', updating
// tmp variable by multiplication
else if (opr.get(k) == '*')
{
minTmp = minVal[i][k]
* minVal[k + 1][j];
maxTmp = maxVal[i][k]
* maxVal[k + 1][j];
}
// updating array values by tmp
// variables
if (minTmp < minVal[i][j])
minVal[i][j] = minTmp;
if (maxTmp > maxVal[i][j])
maxVal[i][j] = maxTmp;
}
}
}
// last element of first row will store the result
System.out.print(
"Minimum value : " + minVal[0][len - 1]
+ ", Maximum value : " + maxVal[0][len - 1]);
}
// Driver code to test above methods
public static void main(String[] args)
{
String expression = "1+2*3+4*5";
printMinAndMaxValueOfExp(expression);
}
}
// This code is contributed by Dharanendra L V.
Python3
# Python3 program to get maximum and minimum
# values of an expression
# Utility method to check whether a character
# is operator or not
def isOperator(op):
return (op == '+' or op == '*')
# method prints minimum and maximum value
# obtainable from an expression
def printMinAndMaxValueOfExp(exp):
num = []
opr = []
tmp = ""
# store operator and numbers in different vectors
for i in range(len(exp)):
if (isOperator(exp[i])):
opr.append(exp[i])
num.append(int(tmp))
tmp = ""
else:
tmp += exp[i]
# storing last number in vector
num.append(int(tmp))
llen = len(num)
minVal = [[ 0 for i in range(llen)] for i in range(llen)]
maxVal = [[ 0 for i in range(llen)] for i in range(llen)]
# initializing minval and maxval 2D array
for i in range(llen):
for j in range(llen):
minVal[i][j] = 10**9
maxVal[i][j] = 0
# initializing main diagonal by num values
if (i == j):
minVal[i][j] = maxVal[i][j] = num[i]
# looping similar to matrix chain multiplication
# and updating both 2D arrays
for L in range(2, llen + 1):
for i in range(llen - L + 1):
j = i + L - 1
for k in range(i, j):
minTmp = 0
maxTmp = 0
# if current operator is '+', updating tmp
# variable by addition
if(opr[k] == '+'):
minTmp = minVal[i][k] + minVal[k + 1][j]
maxTmp = maxVal[i][k] + maxVal[k + 1][j]
# if current operator is '*', updating tmp
# variable by multiplication
else if(opr[k] == '*'):
minTmp = minVal[i][k] * minVal[k + 1][j]
maxTmp = maxVal[i][k] * maxVal[k + 1][j]
# updating array values by tmp variables
if (minTmp < minVal[i][j]):
minVal[i][j] = minTmp
if (maxTmp > maxVal[i][j]):
maxVal[i][j] = maxTmp
# last element of first row will store the result
print("Minimum value : ",minVal[0][llen - 1],", \
Maximum value : ",maxVal[0][llen - 1])
# Driver code
expression = "1+2*3+4*5"
printMinAndMaxValueOfExp(expression)
# This code is contributed by mohit kumar 29
C#
// C# program to get maximum and minimum
// values of an expression
using System;
using System.Collections.Generic;
public class GFG
{
// Utility method to check whether a character
// is operator or not
static bool isOperator(char op)
{
return (op == '+' || op == '*');
}
// method prints minimum and maximum value
// obtainable from an expression
static void printMinAndMaxValueOfExp(string exp)
{
List<int> num = new List<int>();
List<char> opr = new List<char>();
string tmp = "";
// store operator and numbers in different vectors
for (int i = 0; i < exp.Length; i++)
{
if (isOperator(exp[i]))
{
opr.Add(exp[i]);
num.Add(int.Parse(tmp));
tmp = "";
}
else
{
tmp += exp[i];
}
}
// storing last number in vector
num.Add(int.Parse(tmp));
int len = num.Count;
int[,] minVal = new int[len,len];
int[,] maxVal = new int[len,len];
// initializing minval and maxval 2D array
for (int i = 0; i < len; i++)
{
for (int j = 0; j < len; j++)
{
minVal[i, j] = Int32.MaxValue;
maxVal[i, j] = 0;
// initializing main diagonal by num values
if (i == j)
{
minVal[i, j] = maxVal[i, j] = num[i];
}
}
}
// looping similar to matrix chain multiplication
// and updating both 2D arrays
for (int L = 2; L <= len; L++)
{
for (int i = 0; i < len - L + 1; i++)
{
int j = i + L - 1;
for (int k = i; k < j; k++)
{
int minTmp = 0, maxTmp = 0;
// if current operator is '+', updating
// tmp variable by addition
if (opr[k] == '+')
{
minTmp = minVal[i, k] + minVal[k + 1, j];
maxTmp = maxVal[i, k] + maxVal[k + 1, j];
}
// if current operator is '*', updating
// tmp variable by multiplication
else if (opr[k] == '*')
{
minTmp = minVal[i, k] * minVal[k + 1, j];
maxTmp = maxVal[i, k] * maxVal[k + 1, j];
}
// updating array values by tmp
// variables
if (minTmp < minVal[i, j])
minVal[i, j] = minTmp;
if (maxTmp > maxVal[i, j])
maxVal[i, j] = maxTmp;
}
}
}
// last element of first row will store the result
Console.Write("Minimum value : " +
minVal[0, len - 1] +
", Maximum value : " +
maxVal[0,len - 1]);
}
// Driver code to test above methods
static public void Main ()
{
string expression = "1+2*3+4*5";
printMinAndMaxValueOfExp(expression);
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
// JavaScript program to get maximum and minimum
// values of an expression
// Utility method to check whether a character
// is operator or not
function isOperator(op)
{
return (op == '+' || op == '*');
}
// method prints minimum and maximum value
// obtainable from an expression
function printMinAndMaxValueOfExp(exp)
{
let num = [];
let opr = [];
let tmp = "";
// store operator and numbers in different vectors
for (let i = 0; i < exp.length; i++)
{
if (isOperator(exp[i]))
{
opr.push(exp[i]);
num.push(parseInt(tmp));
tmp = "";
}
else
{
tmp += exp[i];
}
}
// storing last number in vector
num.push(parseInt(tmp));
let len = num.length;
let minVal = new Array(len);
let maxVal = new Array(len);
// initializing minval and maxval 2D array
for (let i = 0; i < len; i++)
{
minVal[i]=new Array(len);
maxVal[i]=new Array(len);
for (let j = 0; j < len; j++)
{
minVal[i][j] = Number.MAX_VALUE;
maxVal[i][j] = 0;
// initializing main diagonal by num values
if (i == j)
minVal[i][j] = maxVal[i][j]
= num[i];
}
}
// looping similar to matrix chain multiplication
// and updating both 2D arrays
for (let L = 2; L <= len; L++)
{
for (let i = 0; i < len - L + 1; i++)
{
let j = i + L - 1;
for (let k = i; k < j; k++)
{
let minTmp = 0, maxTmp = 0;
// if current operator is '+', updating
// tmp variable by addition
if (opr[k] == '+')
{
minTmp = minVal[i][k]
+ minVal[k + 1][j];
maxTmp = maxVal[i][k]
+ maxVal[k + 1][j];
}
// if current operator is '*', updating
// tmp variable by multiplication
else if (opr[k] == '*')
{
minTmp = minVal[i][k]
* minVal[k + 1][j];
maxTmp = maxVal[i][k]
* maxVal[k + 1][j];
}
// updating array values by tmp
// variables
if (minTmp < minVal[i][j])
minVal[i][j] = minTmp;
if (maxTmp > maxVal[i][j])
maxVal[i][j] = maxTmp;
}
}
}
// last element of first row will store the result
document.write(
"Minimum value : " + minVal[0][len - 1]
+ ", Maximum value : " + maxVal[0][len - 1]);
}
// Driver code to test above methods
let expression = "1+2*3+4*5";
printMinAndMaxValueOfExp(expression);
// This code is contributed by ab2127
</script>
Producción:
Minimum value : 27, Maximum value : 105
Complejidad de tiempo: O(n^3), ya que tenemos tres bucles anidados en la función.
Complejidad espacial: O(n^2), ya que estamos usando una array 2D para almacenar los valores de todos los subproblemas.
Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA