There are two types of parentheses. Open and close parentheses. In this problem, open parentheses can be like: ‘(‘ and closed parentheses can be like: ‘).’ We put appropriate parenthesis around numbers and operators in an expression to parenthesize it. Parentheses can be used to enforce a particular order of evaluation in expressions that contain multiple operators.
In this article, we’ll learn the different ways to add appropriate parentheses around numbers and operators such that we get different values of the expression.
Problem Statement
You are given a string expression consisting of numbers and operators. Your task is to return all the different values of the expression that can be made by adding parentheses around operators and numbers in all the different ways.
Note: You may return the answer in any order. Also, the operators are only ‘*’, ‘+’, and ‘-’.
For example:
INPUT : s = “2-1-1”
OUTPUT: [0,2]
((2-1)-1) = 0 and (2-(1-1)) = 2. Thus 0 and 2 are the two different values.
INPUT : s = “2*3-4*5”
OUTPUT: [-34,-14,-10,-10,10]
The different ways are:
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10
Recommended: Please try it on “Coding Ninjas Studio” before moving on to the solution approach.
Solution Approach
The main thing you need to understand to solve this problem is that adding parenthesis is just a way to order the operations. That’s precisely why your total values of the expression vary according to the parentheses addition. To consider all ways to put parenthesis, you need to consider all the ways to order operations that you are doing.
Approach 1: Recursion
Imagine you have a function that returns all the possible values of a string s[start,end] where start and end are the start points and endpoints of the string.
Now suppose your string is s1-s2+s3*s4 (s1,s2,s3 and s4 are the numbers in between the operators). Then, when you encounter -, you get all the values to the left of -, store it in a vector called leftVal. Then, similarly, get the values to the right of -, in a vector called rightVal. Then, to find all the different values, we basically have to go through each number in leftVal and subtract it with each number in rightVal. These will be the values for the whole string.
Thus, we can see that the answer for current string depends on the answer of the substrings separated by the operator. Hence, recursion will be used.
Steps are:
Input the string and call the function differentWays.
In the differentWays function, call the recursion function “rec”. The parameters in the rec function are starting index of the passed string, the ending index of the passed string and the string for which we want to calculate the answer. Initially, call the rec function for the whole string, i.e., start=0 and end = n-1.
In the “rec” function,
Declare and initialize an ans vector, which will store the answer for the current string.
Traverse the string from i=start to end position.
If s[i]==’*’ or s[i]==’+’ or s[i]==’-’, this ith character is separating the string in two parts, one from start to i-1 and another from i+1 to end. Call the “rec” function for the string from start to i-1 and store the answer in the leftVal vector. Similarly, do the same for the right part and store the answer in the rightVal vector.
Now, iterate through each value in leftVal and rightVal and do the operation s[i]. Also, keep storing the calculated result in the ans vector.
If the ans vector is empty yet, this means that no operator was encountered. Thus there was just a single number in the string so push that into the ans vector.
Return ans.
Print out the values in the ans vector.
The recursion tree for the expression 2*3-4*5 will look something like this:
C++ implementation
Below is the C++ implementation of the above-discussed steps.
#include <bits/stdc++.h>
using namespace std;
vector<int> rec(string& s, int start, int end){
vector<int> ans; //Declare ans vector for storing the ans
for(int i = start; i <= end; i++){ // Traverse the string from start to end
char c = s[i];
if(c == '*' || c == '+' || c== '-'){ // if s[i] is an operator
// Get the answers for left and right part separated by the operator
vector<int> leftVal = rec(s, start, i - 1);
vector<int> rightVal = rec(s, i + 1, end);
// For each number in leftVal, do the operation with each number in //rightVal
for(auto lVal : leftVal){
for(auto rVal : rightVal){
int temp;
if(c=='*'){
temp = lVal*rVal;
}
else if(c=='+'){
temp = lVal+rVal;
}
else if(c=='-'){
temp = lVal-rVal;
}
ans.push_back(temp); // Push back the calculated temp value
}
}
}
}
// If ans is empty, it means that the string only contains a number and no //operators
// So just convert that number into an interger and push into the ans vector.
if(ans.empty())
ans.push_back(stoi(s.substr(start, end - start + 1)));
// Return ans.
return ans;
}
vector<int> diffWaysToCompute(string s) {
vector<int>res;
if(s.empty()) // If the string is initially empty, return an empty vector
return res;
return rec(s, 0, s.size() - 1);
}
int32_t main(){
string s; // Input the string
cin>>s;
vector<int>ans = diffWaysToCompute(s); // Store the answers in a vector and //print it
for(auto x:ans){
cout<<x<<" ";
}
cout<<endl;
}
You can also try this code with Online C++ Compiler
O((2^(k))*n), where n is the length of the string where k is the number of operators.
Reason: In rec function, for each index i from start to end we’re traversing the string from start to end (costing us O(n) time) and, making two recursive calls each time an operator is called which costs O((2*k)). Thus, the total time complexity is O((2^(k))*n).
In the above recursion approach, we’re calling the rec function for the same substrings many times. Therefore, the time complexity is exponential. The time complexity can be reduced if we use a dp table that stores the results for each substring.
Let’s define a 3-D vector, dp, where dp[i][j] = vector of all possible results for the substring starting from index i and ending at index j. Earlier, when we were returning the ans vector, here, we’ll store the ans vector in dp[start][end] before returning it.
Steps are:
Input the string and call the function differentWays.
In the differentWays function, declare a global 3-D vector dp and call the recursion function “rec”. The parameters in the rec function are starting index of the passed string, the ending index of the passed string, the dp vector, and the string for which we want to calculate the answer. Initially, call the rec function for the whole string, i.e., start=0 and end = n-1.
In the “rec” function,
Check if the answer for this substring is already calculated. If the vector dp[start][end] is not empty, this means that the answer is already calculated. So directly return it. Otherwise, move to the following steps.
Declare and initialize an ans vector, which will store the answer for the current string.
Traverse the string from i=start to end position.
If s[i]==’*’ or s[i]==’+’ or s[i]==’-’, this ith character is separating the string in two parts, one from start to i-1 and another from i+1 to end. Call the “rec” function for the string from start to i-1 and store the answer in the leftVal vector. Similarly, do the same for the right part and store the answer in the rightVal vector.
Now, iterate through each value in leftVal and rightVal and do the operation s[i]. Also, keep storing the calculated result in the ans vector.
If the ans vector is empty yet, this means that no operator was encountered. Thus there was just a single number in the string so push that into the ans vector.
Store the ans vector as the dp value for dp[start][end] and return it.
Print out the values in ans.
C++ implementation
Below is the C++ implementation of the above-discussed steps.
#include <bits/stdc++.h>
using namespace std;
vector<int> rec(string& s, int start, int end,vector<vector<vector<int>>>&dp){
if(!dp[start][end].empty()){ // Check if the answer for this substring is already calculated
return dp[start][end]; // If yes, return it straight away
}
vector<int> ans; //Declare ans vector for storing the ans
for(int i = start; i <= end; i++){ // Traverse the string from start to end
char c = s[i];
if(c == '*' || c == '+' || c== '-'){ // if s[i] is an operator
// Get the answers for left and right part separated by the operator
vector<int> leftVal = rec(s, start, i - 1,dp);
vector<int> rightVal = rec(s, i + 1, end,dp);
// For each number in leftVal, do the operation with each number in rightVal
for(auto lVal : leftVal){
for(auto rVal : rightVal){
int temp;
if(c=='*'){
temp = lVal*rVal;
}
else if(c=='+'){
temp = lVal+rVal;
}
else if(c=='-'){
temp = lVal-rVal;
}
ans.push_back(temp); // Push back the calculated temp value
}
}
}
}
// If ans is empty, it means that the string only contains a number and no operators
// So just convert that number into an interger and push into the ans vector.
if(ans.empty())
ans.push_back(stoi(s.substr(start, end - start + 1)));
// Return ans.
return dp[start][end] = ans; // Store the ans in dp[start][end] and return it
}
vector<int> diffWaysToCompute(string s) {
vector<int>res;
if(s.empty()) // If the string is initially empty, return an empty vector
return res;
int n = s.length();
vector<vector<vector<int>>>dp(n, vector<vector<int>>(n));
return rec(s, 0, s.size() - 1,dp);
}
int32_t main(){
string s; // Input the string
cin>>s;
vector<int>ans = diffWaysToCompute(s); // Store the answers in a vector and print it
for(auto x:ans){
cout<<x<<" ";
}
cout<<endl;
}
You can also try this code with Online C++ Compiler
We put appropriate parenthesis around numbers and operators in an expression to parenthesize it. Parentheses can be used to enforce a particular order of evaluation in expressions that contain multiple operators. We use a parenthesized expression to explicitly specify the order of operations in a complex arithmetic expression.
What is dynamic programming, and where is it used?
Dynamic programming is an optimization method used in various programming problems. It is used in problems where the solution depends on smaller overlapping subproblems. We use it to memorize the results so that they can easily be used later when needed.
What are overlapping subproblems?
A problem has overlapping subproblems if it can be divided into smaller problems that are reused multiple times.
What is a balanced parentheses string?
A string of parentheses is intuitively balanced if each left parentheses have matching right parentheses and the matched pairs are well nested.
Where can I submit my “Different ways to add parentheses” problem?
You can submit your code on Coding Ninjas Studio here and get it accepted right away.
Are there more Data Structures and Algorithms problems in Coding Ninjas Studio?
Yes, Coding Ninjas Studio is a platform that provides both practice coding questions and commonly asked interview questions. The more we’ll practice, the better our chances are of getting into a dream company of ours.
I would suggest you solve them to gain more confidence on these topics. These questions are asked during various coding contests as well as placement tests.
117+ registered 