Dada una array arr[] que consta de N strings , la tarea es encontrar la suma total de la array brr[] ( inicialmente vacía ) construida realizando las siguientes operaciones mientras se recorre la array dada arr[] :
- Si la array arr[] contiene un entero, inserte ese entero en la array brr[] .
- Si la array arr[] tiene la string “+” , inserte la suma de los dos últimos elementos de la array brr[] en la array brr[] .
- Si la array arr[] tiene la string «D» , inserte el valor que es el doble del último elemento de la array brr[] en la array brr[] .
- Si la array arr[] tiene la string «C» , entonces elimine el último elemento de la array brr[] a la array brr[] .
Ejemplos:
Entrada: arr[] = {“5”, “2”, “C”, “D”, “+”}
Salida: 30
Explicación:
Mientras se recorre el arreglo arr[] , el arreglo brr[] se modifica como:
- “5”: agrega 5 a la array brr[]. Ahora, la array brr[] se modifica a {5}.
- “2”: agrega 2 a la array brr[]. Ahora, la array brr[] se modifica a {5, 2}.
- “C”: elimina el último elemento de la array brr[]. Ahora, la array brr[] se modifica a {5}.
- “D”: agrega dos veces el último elemento de la array brr[] a la array brr[]. Ahora, la array brr[] se modifica a {5, 10}.
- “+”: agregue la suma de los dos últimos elementos de la array brr[] a la array brr[]. Ahora la array brr[] se modifica a {5, 10, 15}.
Después de realizar las operaciones anteriores, la suma total de la array brr[] es 5 + 10 + 15 = 30.
Entrada: arr[] = {“5”, “-2”, “4”, “C”, “D”, “9”, “+”, “+”}
Salida: 27
Enfoque: La idea para resolver el problema dado es usar un Stack . Siga los pasos a continuación para resolver el problema:
- Inicialice una pila de enteros, digamos S , e inicialice una variable, digamos ans como 0 , para almacenar la suma resultante de la array formada.
- Recorra la array dada arr[] y realice los siguientes pasos:
- Si el valor de arr[i] es «C» , entonces reste el elemento superior de la pila de ans y sáquelo de S.
- Si el valor de arr[i] es «D» , entonces empuje dos veces el elemento superior de la pila S en la pila S y luego agregue su valor a ans .
- Si el valor de arr[i] es “+” , entonces empuje el valor de la suma de los dos elementos superiores de la pila S y agregue su suma a ans .
- De lo contrario, inserte arr[i] en la pila S y agregue su valor a ans .
- Después del bucle, imprime el valor de ans como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the sum of the array
// formed by performing given set of
// operations while traversing the array ops[]
void findTotalSum(vector<string>& ops)
{
// If the size of array is 0
if (ops.empty()) {
cout << 0;
return;
}
stack<int> pts;
// Stores the required sum
int ans = 0;
// Traverse the array ops[]
for (int i = 0; i < ops.size(); i++) {
// If the character is C, remove
// the top element from the stack
if (ops[i] == "C") {
ans -= pts.top();
pts.pop();
}
// If the character is D, then push
// 2 * top element into stack
else if (ops[i] == "D") {
pts.push(pts.top() * 2);
ans += pts.top();
}
// If the character is +, add sum
// of top two elements from the stack
else if (ops[i] == "+") {
int a = pts.top();
pts.pop();
int b = pts.top();
pts.push(a);
ans += (a + b);
pts.push(a + b);
}
// Otherwise, push x
// and add it to ans
else {
int n = stoi(ops[i]);
ans += n;
pts.push(n);
}
}
// Print the resultant sum
cout << ans;
}
// Driver Code
int main()
{
vector<string> arr = { "5", "-2", "C", "D", "+" };
findTotalSum(arr);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG
{
// Function to find the sum of the array
// formed by performing given set of
// operations while traversing the array ops[]
static void findTotalSum(String ops[])
{
// If the size of array is 0
if (ops.length == 0)
{
System.out.println(0);
return;
}
Stack<Integer> pts = new Stack<>();
// Stores the required sum
int ans = 0;
// Traverse the array ops[]
for (int i = 0; i < ops.length; i++) {
// If the character is C, remove
// the top element from the stack
if (ops[i] == "C") {
ans -= pts.pop();
}
// If the character is D, then push
// 2 * top element into stack
else if (ops[i] == "D") {
pts.push(pts.peek() * 2);
ans += pts.peek();
}
// If the character is +, add sum
// of top two elements from the stack
else if (ops[i] == "+") {
int a = pts.pop();
int b = pts.peek();
pts.push(a);
ans += (a + b);
pts.push(a + b);
}
// Otherwise, push x
// and add it to ans
else {
int n = Integer.parseInt(ops[i]);
ans += n;
pts.push(n);
}
}
// Print the resultant sum
System.out.println(ans);
}
// Driver Code
public static void main(String[] args)
{
String arr[] = { "5", "-2", "C", "D", "+" };
findTotalSum(arr);
}
}
// This code is contributed by Kingash.
Python3
# Python3 program for the above approach # Function to find the sum of the array # formed by performing given set of # operations while traversing the array ops[] def findTotalSum(ops): # If the size of array is 0 if (len(ops) == 0): print(0) return pts = [] # Stores the required sum ans = 0 # Traverse the array ops[] for i in range(len(ops)): # If the character is C, remove # the top element from the stack if (ops[i] == "C"): ans -= pts[-1] pts.pop() # If the character is D, then push # 2 * top element into stack elif (ops[i] == "D"): pts.append(pts[-1] * 2) ans += pts[-1] # If the character is +, add sum # of top two elements from the stack elif (ops[i] == "+"): a = pts[-1] pts.pop() b = pts[-1] pts.append(a) ans += (a + b) pts.append(a + b) # Otherwise, push x # and add it to ans else: n = int(ops[i]) ans += n pts.append(n) # Print the resultant sum print(ans) # Driver Code if __name__ == "__main__": arr = ["5", "-2", "C", "D", "+"] findTotalSum(arr) # This code is contributed by ukasp.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the sum of the array
// formed by performing given set of
// operations while traversing the array ops[]
static void findTotalSum(string []ops)
{
// If the size of array is 0
if (ops.Length == 0)
{
Console.WriteLine(0);
return;
}
Stack<int> pts = new Stack<int>();
// Stores the required sum
int ans = 0;
// Traverse the array ops[]
for(int i = 0; i < ops.Length; i++)
{
// If the character is C, remove
// the top element from the stack
if (ops[i] == "C")
{
ans -= pts.Pop();
}
// If the character is D, then push
// 2 * top element into stack
else if (ops[i] == "D")
{
pts.Push(pts.Peek() * 2);
ans += pts.Peek();
}
// If the character is +, add sum
// of top two elements from the stack
else if (ops[i] == "+")
{
int a = pts.Pop();
int b = pts.Peek();
pts.Push(a);
ans += (a + b);
pts.Push(a + b);
}
// Otherwise, push x
// and add it to ans
else
{
int n = Int32.Parse(ops[i]);
ans += n;
pts.Push(n);
}
}
// Print the resultant sum
Console.WriteLine(ans);
}
// Driver Code
public static void Main()
{
string []arr = { "5", "-2", "C", "D", "+" };
findTotalSum(arr);
}
}
// This code is contributed by ipg2016107
Javascript
<script>
// JavaScript program for the above approach
// Function to find the sum of the array
// formed by performing given set of
// operations while traversing the array ops[]
function findTotalSum(ops)
{
// If the size of array is 0
if (ops.length==0) {
document.write( 0);
return;
}
var pts = [];
// Stores the required sum
var ans = 0;
// Traverse the array ops[]
for (var i = 0; i < ops.length; i++) {
// If the character is C, remove
// the top element from the stack
if (ops[i] == "C") {
ans -= pts[pts.length-1];
pts.pop();
}
// If the character is D, then push
// 2 * top element into stack
else if (ops[i] == "D") {
pts.push(pts[pts.length-1] * 2);
ans += pts[pts.length-1];
}
// If the character is +, add sum
// of top two elements from the stack
else if (ops[i] == "+") {
var a = pts[pts.length-1];
pts.pop();
var b = pts[pts.length-1];
pts.push(a);
ans += (a + b);
pts.push(a + b);
}
// Otherwise, push x
// and add it to ans
else {
var n = parseInt(ops[i]);
ans += n;
pts.push(n);
}
}
// Print the resultant sum
document.write( ans);
}
// Driver Code
var arr = ["5", "-2", "C", "D", "+" ];
findTotalSum(arr);
</script>
Producción:
30
Complejidad temporal: O(N)
Espacio auxiliar: O(N)