# Intuition\nWhen we try to evaluate a operator, we again encounter the same problem on the left & right substring of the operator & as we have to calculate all possible ways, that\'s where recursion comes in picture.\n\n# Recursion\nWe define a recursive function `getDiffWays` where, `getDiffWays(i, j)` returns us number of ways to evaluate `expression[i...j]`. therefore our answer will be `getDiffWays(0, n - 1)`. where, `n` is the length of string `expression`.\n\n## Code\n```C++ []\nclass Solution {\n bool isOperator(char ch) {\n return (ch == \'+\' || ch == \'-\' || ch == \'*\');\n }\n\n vector getDiffWays(int i, int j, string& expression) {\n \n // If length of the substring is 1 or 2\n // we encounter our base case i.e. a number found.\n int len = j - i + 1;\n if(len <= 2) {\n return { stoi(expression.substr(i, len)) };\n }\n\n // If it is not a number then it is an expression\n // now we try to evaluate every opertor present in it\n vector res;\n for(int ind = i; ind <= j; ind++) {\n if(isOperator(expression[ind])) {\n char op = expression[ind];\n\n // if char at ind is operator \n // get all results for its left and right substring using recursion\n vector left = getDiffWays(i, ind - 1, expression);\n vector right = getDiffWays(ind + 1, j, expression);\n\n // try all options for left & right operand\n // and push all results to the answer\n for(int l : left) {\n for(int r : right) {\n if(op == \'+\') {\n res.push_back(l + r);\n }\n else if(op == \'-\') {\n res.push_back(l - r);\n }\n else if(op == \'*\') {\n res.push_back(l * r);\n }\n }\n }\n }\n }\n return res;\n }\n\npublic:\n vector diffWaysToCompute(string expression) {\n int n = expression.size();\n return getDiffWays(0, n - 1, expression);\n }\n};\n\n```\n```Java []\nclass Solution {\n private boolean isOperator(char ch) {\n return (ch == \'+\' || ch == \'-\' || ch == \'*\');\n }\n\n private List getDiffWays(int i, int j, String expression) {\n int len = j - i + 1;\n List res = new ArrayList<>();\n\n // If length of the substring is 1 or 2\n // we encounter our base case i.e. a number found.\n if (len <= 2) {\n res.add(Integer.parseInt(expression.substring(i, i + len)));\n return res;\n }\n\n // If it is not a number then it is an expression\n // now we try to evaluate every opertor present in it\n for (int ind = i; ind <= j; ind++) {\n if (isOperator(expression.charAt(ind))) {\n char op = expression.charAt(ind);\n\n // if char at ind is operator \n // get all results for its left and right substring using recursion\n List left = getDiffWays(i, ind - 1, expression);\n List right = getDiffWays(ind + 1, j, expression);\n\n // try all options for left & right operand\n // and push all results to the answer\n for (int l : left) {\n for (int r : right) {\n if (op == \'+\') {\n res.add(l + r);\n } else if (op == \'-\') {\n res.add(l - r);\n } else if (op == \'*\') {\n res.add(l * r);\n }\n }\n }\n }\n }\n return res;\n }\n\n public List diffWaysToCompute(String expression) {\n int n = expression.length();\n return getDiffWays(0, n - 1, expression);\n }\n}\n\n```\n``` Python3 []\nclass Solution:\n def isOperator(self, ch):\n return ch == \'+\' or ch == \'-\' or ch == \'*\'\n\n def getDiffWays(self, i, j, expression):\n res = []\n\n # If length of the substring is 1 or 2\n # we encounter our base case i.e. a number found.\n if j - i + 1 <= 2:\n res.append(int(expression[i:j + 1]))\n return res\n\n # If it is not a number then it is an expression\n # now we try to evaluate every opertor present in it\n for ind in range(i, j + 1):\n if self.isOperator(expression[ind]):\n op = expression[ind]\n \n # if char at ind is operator \n # get all results for its left and right substring using recursion\n left = self.getDiffWays(i, ind - 1, expression)\n right = self.getDiffWays(ind + 1, j, expression)\n\n # try all options for left & right operand\n # and push all results to the answer\n for l in left:\n for r in right:\n if op == \'+\':\n res.append(l + r)\n elif op == \'-\':\n res.append(l - r)\n elif op == \'*\':\n res.append(l * r)\n\n return res\n\n def diffWaysToCompute(self, expression: str):\n n = len(expression)\n return self.getDiffWays(0, n - 1, expression)\n\n```\n\n## Complexity\n- Time complexity:\n$$Exponential$$, it\'s very hard to derive exact Time complexity of the solution but it will be definitely exponential in nature.\n\n- Space complexity:\n$$O(n \\cdot x)$$ for recursion stack. where, `x` is the number of ways to calcuate the expression which is $operators!$\n\n# Memoization\nIf we dry run a example, we observe overalapping subproblems that gets calculated again & again. We can avoid this by introducing a 3D DP array / cache & storing the results we calculate so that we don\'t need to process same stuff again & again.\n\n## Code\n```C++ []\nclass Solution {\n bool isOperator(char ch) {\n return (ch == \'+\' || ch == \'-\' || ch == \'*\');\n }\n\n vector getDiffWays(int i, int j, vector>>& dp, string& expression) {\n\n // Return cached result if already calculated\n if(!dp[i][j].empty()) {\n return dp[i][j];\n }\n \n // If length of the substring is 1 or 2\n // we encounter our base case i.e. a number found.\n int len = j - i + 1;\n if(len <= 2) {\n return dp[i][j] = { stoi(expression.substr(i, len)) };\n }\n\n // If it is not a number then it is an expression\n // now we try to evaluate every opertor present in it\n vector res;\n for(int ind = i; ind <= j; ind++) {\n if(isOperator(expression[ind])) {\n char op = expression[ind];\n\n // if char at ind is operator \n // get all results for its left and right substring using recursion\n vector left = getDiffWays(i, ind - 1, dp, expression);\n vector right = getDiffWays(ind + 1, j, dp, expression);\n\n // try all options for left & right operand\n // and push all results to the answer\n for(int l : left) {\n for(int r : right) {\n if(op == \'+\') {\n res.push_back(l + r);\n }\n else if(op == \'-\') {\n res.push_back(l - r);\n }\n else if(op == \'*\') {\n res.push_back(l * r);\n }\n }\n }\n }\n }\n return dp[i][j] = res;\n }\n\npublic:\n vector diffWaysToCompute(string expression) {\n int n = expression.size();\n vector>> dp(n, vector>(n));\n return getDiffWays(0, n - 1, dp, expression);\n }\n};\n```\n```Java []\nclass Solution {\n private boolean isOperator(char ch) {\n return (ch == \'+\' || ch == \'-\' || ch == \'*\');\n }\n\n private List getDiffWays(int i, int j, Map> dp, String expression) {\n String key = i + "-" + j;\n\n // Return cached result if already calculated\n if (dp.containsKey(key)) {\n return dp.get(key);\n }\n\n // If length of the substring is 1 or 2\n // we encounter our base case i.e. a number found.\n int len = j - i + 1;\n if (len <= 2) {\n List result = new ArrayList<>();\n result.add(Integer.parseInt(expression.substring(i, j + 1)));\n dp.put(key, result);\n return result;\n }\n\n // If it is not a number then it is an expression\n // now we try to evaluate every operator present in it\n List res = new ArrayList<>();\n for (int ind = i; ind <= j; ind++) {\n if (isOperator(expression.charAt(ind))) {\n char op = expression.charAt(ind);\n\n // if char at ind is an operator \n // get all results for its left and right substring using recursion\n List left = getDiffWays(i, ind - 1, dp, expression);\n List right = getDiffWays(ind + 1, j, dp, expression);\n\n // try all options for left & right operand\n // and push all results to the answer\n for (int l : left) {\n for (int r : right) {\n if (op == \'+\') {\n res.add(l + r);\n } else if (op == \'-\') {\n res.add(l - r);\n } else if (op == \'*\') {\n res.add(l * r);\n }\n }\n }\n }\n }\n dp.put(key, res);\n return res;\n }\n\n public List diffWaysToCompute(String expression) {\n Map> dp = new HashMap<>();\n return getDiffWays(0, expression.length() - 1, dp, expression);\n }\n}\n\n```\n```Python3 []\nclass Solution:\n def isOperator(self, ch):\n return ch == \'+\' or ch == \'-\' or ch == \'*\'\n\n def getDiffWays(self, i, j, dp, expression):\n\n # Return cached result if already calculated\n if (i, j) in dp:\n return dp[(i, j)]\n\n # If length of the substring is 1 or 2\n # we encounter our base case i.e. a number found.\n len_substring = j - i + 1\n if len_substring <= 2:\n result = [int(expression[i:j+1])]\n dp[(i, j)] = result\n return result\n\n # If it is not a number then it is an expression\n # now we try to evaluate every operator present in it\n res = []\n for ind in range(i, j + 1):\n if self.isOperator(expression[ind]):\n op = expression[ind]\n\n # if char at ind is an operator \n # get all results for its left and right substring using recursion\n left = self.getDiffWays(i, ind - 1, dp, expression)\n right = self.getDiffWays(ind + 1, j, dp, expression)\n\n # try all options for left & right operand\n # and push all results to the answer\n for l in left:\n for r in right:\n if op == \'+\':\n res.append(l + r)\n elif op == \'-\':\n res.append(l - r)\n elif op == \'*\':\n res.append(l * r)\n\n dp[(i, j)] = res\n return res\n\n def diffWaysToCompute(self, expression: str):\n dp = {}\n return self.getDiffWays(0, len(expression) - 1, dp, expression)\n```\n\n## Complexity\n- Time complexity:\n$$O(n^2 \\cdot (n \\cdot x^2))$$, as there are approx. $n^2$ states and to calculate these states 3 nested loops in recursive function take $O(n * x^2)$ time.\n\n- Space complexity:\n$$O(n \\cdot x) + O(n^2 \\cdot x)$$ for recursion stack & dp array. where, `x` is the number of ways to calcuate the expression which is $operators!$\n\n# Tabulation\nWe can eliminate the recursion stack space used in memoization solution by just calculating result for every valid expression substring in bottom up manner i.e. Tabulation.\n\nIn memoization, every substring which gets called recursively is valid but in this solution we need to check if given substring is a valid arithemetic expression or not.\n\n## Code\n``` C++ []\nclass Solution {\n bool isOperator(char ch) {\n return (ch == \'+\' || ch == \'-\' || ch == \'*\');\n }\n\npublic:\n vector diffWaysToCompute(string expression) {\n int n = expression.size();\n vector>> dp(n, vector>(n));\n\n // Function to check if given substring of expression\n // is a valid expression\n auto isValidExpression = [&](int i, int j) -> bool {\n return (i == 0 || isOperator(expression[i - 1])) && (j == n - 1 || isOperator(expression[j + 1]));\n };\n\n // get answer for all single digit numbers\n for(int i = 0; i < n; i++) {\n if(isValidExpression(i, i)) {\n dp[i][i] = { stoi(expression.substr(i, 1)) };\n }\n }\n\n // get answer for all 2 digit numbers\n for(int i = 0, j = 1; j < n; i++, j++) {\n if(isValidExpression(i, j)) {\n dp[i][j] = { stoi(expression.substr(i, 2)) };\n }\n }\n\n // get answer for all valid expression substrings in bottom up manner\n for(int len = 3; len <= n; len++) {\n for(int i = 0, j = i + len - 1; j < n; i++, j++) {\n if(!isValidExpression(i, j))\n continue;\n\n // Try to evaluate every operator\n for(int ind = i; ind <= j; ind++) {\n if(isOperator(expression[ind])) {\n char op = expression[ind];\n\n // if char at ind is operator \n // get all results for its left and right substring\n vector left = dp[i][ind - 1];\n vector right = dp[ind + 1][j];\n\n // try all options for left & right operand\n // and push all results to the answer\n for(int l : left) {\n for(int r : right) {\n if(op == \'+\') {\n dp[i][j].push_back(l + r);\n }\n else if(op == \'-\') {\n dp[i][j].push_back(l - r);\n }\n else if(op == \'*\') {\n dp[i][j].push_back(l * r);\n }\n }\n }\n }\n } \n }\n }\n\n return dp[0][n - 1];\n }\n};\n```\n``` Java []\nimport java.util.*;\n\nclass Solution {\n private boolean isOperator(char ch) {\n return (ch == \'+\' || ch == \'-\' || ch == \'*\');\n }\n\n public List diffWaysToCompute(String expression) {\n int n = expression.length();\n List[][] dp = new ArrayList[n][n];\n\n // Function to check if given substring of expression\n // is a valid expression\n BiFunction isValidExpression = (i, j) -> \n (i == 0 || isOperator(expression.charAt(i - 1))) && \n (j == n - 1 || isOperator(expression.charAt(j + 1)));\n\n // Get answer for all single digit numbers\n for (int i = 0; i < n; i++) {\n if (isValidExpression.apply(i, i)) {\n dp[i][i] = new ArrayList<>();\n dp[i][i].add(Integer.parseInt(expression.substring(i, i + 1)));\n }\n }\n\n // Get answer for all 2 digit numbers\n for (int i = 0, j = 1; j < n; i++, j++) {\n if (isValidExpression.apply(i, j)) {\n dp[i][j] = new ArrayList<>();\n dp[i][j].add(Integer.parseInt(expression.substring(i, i + 2)));\n }\n }\n\n // Get answer for all valid expression substrings in bottom up manner\n for (int len = 3; len <= n; len++) {\n for (int i = 0, j = i + len - 1; j < n; i++, j++) {\n if (!isValidExpression.apply(i, j)) {\n continue;\n }\n\n dp[i][j] = new ArrayList<>();\n // Try to evaluate every operator\n for (int ind = i; ind <= j; ind++) {\n if (isOperator(expression.charAt(ind))) {\n char op = expression.charAt(ind);\n\n // If char at ind is operator, get all results for its left and right substrings\n List left = dp[i][ind - 1];\n List right = dp[ind + 1][j];\n\n // Try all options for left & right operands and add all results to the answer\n for (int l : left) {\n for (int r : right) {\n if (op == \'+\') {\n dp[i][j].add(l + r);\n } else if (op == \'-\') {\n dp[i][j].add(l - r);\n } else if (op == \'*\') {\n dp[i][j].add(l * r);\n }\n }\n }\n }\n }\n }\n }\n\n return dp[0][n - 1];\n }\n}\n```\n``` Python3 []\nclass Solution:\n def isOperator(self, ch):\n return ch == \'+\' or ch == \'-\' or ch == \'*\'\n\n def diffWaysToCompute(self, expression: str) -> List[int]:\n n = len(expression)\n dp = [[[] for _ in range(n)] for _ in range(n)]\n\n def isValidExpression(i, j):\n return (i == 0 or self.isOperator(expression[i - 1])) and (j == n - 1 or self.isOperator(expression[j + 1]))\n\n # Get answer for all single digit numbers\n for i in range(n):\n if isValidExpression(i, i):\n dp[i][i] = [int(expression[i])]\n\n # Get answer for all 2 digit numbers\n for i in range(n - 1):\n if isValidExpression(i, i + 1):\n dp[i][i + 1] = [int(expression[i:i + 2])]\n\n # Get answer for all valid expression substrings in bottom-up manner\n for length in range(3, n + 1):\n for i in range(n - length + 1):\n j = i + length - 1\n if not isValidExpression(i, j):\n continue\n\n dp[i][j] = []\n # Try to evaluate every operator\n for ind in range(i, j + 1):\n if self.isOperator(expression[ind]):\n op = expression[ind]\n\n # If char at ind is operator, get all results for its left and right substrings\n left = dp[i][ind - 1]\n right = dp[ind + 1][j]\n\n # Try all options for left & right operands and add all results to the answer\n for l in left:\n for r in right:\n if op == \'+\':\n dp[i][j].append(l + r)\n elif op == \'-\':\n dp[i][j].append(l - r)\n elif op == \'*\':\n dp[i][j].append(l * r)\n\n return dp[0][n - 1]\n```\n\n## Complexity\n- Time complexity:\n$$O(n^3 \\cdot x^2)$$, same as memoization solution.\n\n- Space complexity:\n$$O(n^2 \\cdot x)$$ for dp array. where, `x` is the number of ways to calcuate the expression which is `operators!`\n

Different Ways to Add Parentheses

Problem Description

Problem Description

Answer Panel