Given an array arr[] consisting of N strings, the task is to find the total sum of the array brr[] (initially empty) constructed by performing following operations while traversing the given array arr[]:
- If the array arr[] contains an integer, then insert that integer into the array brr[].
- If the array arr[] has the string “+”, then insert the sum of the last two elements in the array brr[] into the array brr[].
- If the array arr[] has the string “D”, then insert the value which is twice the last element of the array brr[] to the array brr[].
- If the array arr[] has the string “C”, then remove the last element of the array brr[] to the array brr[].
Examples:
Input: arr[] = {“5”, “2”, “C”, “D”, “+”}
Output: 30
Explanation:
While traversing the array arr[], the array brr[] is modified as:
- “5” – Add 5 to the array brr[]. Now, the array brr[] modifies to {5}.
- “2” – Add 2 to the array brr[]. Now, the array brr[] modifies to {5, 2}.
- “C” – Remove the last element from the array brr[]. Now, the array brr[] modifies to {5}.
- “D” – Add twice the last element of the array brr[] to the array brr[]. Now, the array brr[] modifies to {5, 10}.
- “+” – Add the sum of the last two elements of the array brr[] to the array brr[]. Now the array brr[] modifies to {5, 10, 15}.
After performing the above operations, the total sum of the array brr[] is 5 + 10 + 15 = 30.
Input: arr[] = {“5”, “-2”, “4”, “C”, “D”, “9”, “+”, “+”}
Output: 27
Approach: The idea to solve the given problem is to use a Stack. Follow the steps below to solve the problem:
- Initialize a stack of integers, say S, and initialize a variable, say ans as 0, to store the resultant sum of the array formed.
- Traverse the given array arr[] and perform the following steps:
- If the value of arr[i] is “C”, then subtract the top element of the stack from the ans and pop it from S.
- If the value of arr[i] is “D”, then push twice the top element of the stack S in the stack S and then add its value to ans.
- If the value of arr[i] is “+”, then push the value of the sum of the top two elements of the stack S and add their sum to ans.
- Otherwise, push arr[i] to the stack S, and add its value to ans.
- After the loop, print the value of ans as the result.
Below is the implementation of the above approach:
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 Codeint main(){ vector<string> arr = { "5", "-2", "C", "D", "+" }; findTotalSum(arr); return 0;} |
Java
// Java program for the above approachimport 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 Codeif __name__ == "__main__": arr = ["5", "-2", "C", "D", "+"] findTotalSum(arr) # This code is contributed by ukasp. |
C#
// C# program for the above approachusing 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 Codepublic 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 Codevar arr = ["5", "-2", "C", "D", "+" ];findTotalSum(arr);</script> |
Output:
30
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
