Given a string that represents an expression constituting numbers and binary operator +, – and * only. We need to parenthesize the expression in all possible way and return all evaluated values.
Input : expr = “3-2-1”
Output : {0, 2}
((3-2)-1) = 0
(3-(2-1)) = 2
Input : expr = "5*4-3*2"
Output : {-10, 10, 14, 10, 34}
(5*(4-(3*2))) = -10
(5*((4-3)*2)) = 10
((5*4)-(3*2)) = 14
((5*(4-3))*2) = 10
(((5*4)-3)*2) = 34
We can solve this problem by parenthesizing all possible valid substring of the expression and then evaluating them, but as we can see that it will involve solving lots of repeating subproblem, to save ourselves we can follow a dynamic programming approach. We store the result for each substring in a map and if string in recursion is already solved, we return result from map instead of solving that again. Below code runs a loop in the string and if at any instant, character is operator then we divide the input from there, recursively solve each part and then combine the result in all possible ways. See the use of c_str() function, this function converts the C++ string into C char array, this function is used in below code because atoi() function expects a character array as an argument not the string. It converts character array to number.
A
C++
// C++ program to output all possible values of// an expression by parenthesizing it.#include <bits/stdc++.h>using namespace std;// method checks, character is operator or notbool isOperator(char op){ return (op == '+' || op == '-' || op == '*');}// Utility recursive method to get all possible// result of input stringvector<int> possibleResultUtil(string input, map< string, vector<int> > memo){ // If already calculated, then return from memo if (memo.find(input) != memo.end()) return memo[input]; vector<int> res; for (int i = 0; i < input.size(); i++) { if (isOperator(input[i])) { // If character is operator then split and // calculate recursively vector<int> resPre = possibleResultUtil(input.substr(0, i), memo); vector<int> resSuf = possibleResultUtil(input.substr(i + 1), memo); // Combine all possible combination for (int j = 0; j < resPre.size(); j++) { for (int k = 0; k < resSuf.size(); k++) { if (input[i] == '+') res.push_back(resPre[j] + resSuf[k]); else if (input[i] == '-') res.push_back(resPre[j] - resSuf[k]); else if (input[i] == '*') res.push_back(resPre[j] * resSuf[k]); } } } } // if input contains only number then save that // into res vector if (res.size() == 0) res.push_back(atoi(input.c_str())); // Store in memo so that input string is not // processed repeatedly memo[input] = res; return res;}// method to return all possible output // from input expressionvector<int> possibleResult(string input){ map< string, vector<int> > memo; return possibleResultUtil(input, memo);}// Driver code to test above methodsint main(){ string input = "5*4-3*2"; vector<int> res = possibleResult(input); for (int i = 0; i < res.size(); i++) cout << res[i] << " "; return 0;} |
Python3
# Python program to output all possible values of# an expression by parenthesizing it.# method checks, character is operator or notdef isOperator(op): return (op == '+' or op == '-' or op == '*')# Utility recursive method to get all possible# result of input stringdef possibleResultUtil(input, memo): # If already calculated, then return from memo if input in memo: return memo[input] res = [] for i in range(len(input)): if isOperator(input[i]): # If character is operator then split and # calculate recursively resPre = possibleResultUtil(input[:i], memo) resSuf = possibleResultUtil(input[i+1:], memo) # Combine all possible combination for j in range(len(resPre)): for k in range(len(resSuf)): if input[i] == '+': res.append(resPre[j] + resSuf[k]) elif input[i] == '-': res.append(resPre[j] - resSuf[k]) elif input[i] == '*': res.append(resPre[j] * resSuf[k]) # if input contains only number then save that # into res list if len(res) == 0: res.append(int(input)) # Store in memo so that input string is not # processed repeatedly memo[input] = res return res# method to return all possible output # from input expressiondef possibleResult(input): memo = {} return possibleResultUtil(input, memo)# Driver code to test above methodsif __name__ == '__main__': input = "5*4-3*2" res = possibleResult(input) for i in range(len(res)): print(res[i], end=' ') |
C#
using System;using System.Collections.Generic;class Program{ // method checks, character is operator or not static bool isOperator(char op) { return (op == '+' || op == '-' || op == '*'); } // Utility recursive method to get all possible // result of input string static List<int> possibleResultUtil(string input, Dictionary<string, List<int>> memo) { // If already calculated, then return from memo if (memo.ContainsKey(input)) return memo[input]; List<int> res = new List<int>(); for (int i = 0; i < input.Length; i++) { if (isOperator(input[i])) { // If character is operator then split and // calculate recursively List<int> resPre = possibleResultUtil(input.Substring(0, i), memo); List<int> resSuf = possibleResultUtil(input.Substring(i + 1), memo); // Combine all possible combination for (int j = 0; j < resPre.Count; j++) { for (int k = 0; k < resSuf.Count; k++) { if (input[i] == '+') res.Add(resPre[j] + resSuf[k]); else if (input[i] == '-') res.Add(resPre[j] - resSuf[k]); else if (input[i] == '*') res.Add(resPre[j] * resSuf[k]); } } } } // if input contains only number then save that // into res vector if (res.Count == 0) res.Add(int.Parse(input)); // Store in memo so that input string is not // processed repeatedly memo[input] = res; return res; } // method to return all possible output // from input expression static List<int> possibleResult(string input) { Dictionary<string, List<int>> memo = new Dictionary<string, List<int>>(); return possibleResultUtil(input, memo); } // Driver code to test above methods static void Main(string[] args) { string input = "5*4-3*2"; List<int> res = possibleResult(input); for (int i = 0; i < res.Count; i++) Console.Write(res[i] + " "); Console.ReadLine(); }}// ksam24000 |
Output:
-10 10 14 10 34
This article is contributed by Utkarsh Trivedi. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
