Definition
- Evaluate Expression – also called Different Ways to Add Parentheses; compute all possible results from all valid parenthesizations of an arithmetic expression.
- Divide-and-conquer – at each operator, split into left and right sub-expressions, recursively compute all results of each, and combine every left with every right using the operator.
- Base case – a substring with no operator is a plain number, returning a single-element list.
- Memoization – cache results by substring key to avoid recomputing overlapping sub-problems.
- Catalan growth – the number of groupings is the Catalan number for (n-1) operators, growing exponentially.
At the National Bank of India, a fee formula like a * b + c can be computed in different groupings: (a * b) + c or a * (b + c). Different groupings can give different totals. The finance team wants every possible total so they can see the range a formula produces.
Understanding the Concepts
What is the Evaluate Expression problem?
Given a string expression containing numbers and the operators +, -, and *, compute all possible results from all valid ways of grouping (parenthesizing) the expression. Return them as a list.
At National Bank of India, a fee formula like "2*3-4*5" can be grouped as ((2*3)-(4*5)) = -14 or (2*(3-(4*5))) = -34 and other ways. Finance wants every possible result to see the range.
package com.bank.formula;
import java.util.*;
public class DiffWaysToCompute {
public static void main(String[] args) {
List<Integer> results = diffWaysToCompute("2*3-4*5");
Collections.sort(results);
System.out.println("All results: " + results);
}
static Map<String, List<Integer>> memo = new HashMap<>();
static List<Integer> diffWaysToCompute(String expr) {
if (memo.containsKey(expr)) return memo.get(expr);
List<Integer> results = new ArrayList<>();
for (int i = 0; i < expr.length(); i++) {
char c = expr.charAt(i);
if (c == '+' || c == '-' || c == '*') {
List<Integer> left = diffWaysToCompute(expr.substring(0, i));
List<Integer> right = diffWaysToCompute(expr.substring(i + 1));
for (int l : left) {
for (int r : right) {
results.add(apply(l, r, c));
}
}
}
}
if (results.isEmpty()) {
results.add(Integer.parseInt(expr)); // base case: plain number
}
memo.put(expr, results);
return results;
}
static int apply(int a, int b, char op) {
return switch (op) {
case '+' -> a + b;
case '-' -> a - b;
case '*' -> a * b;
default -> throw new IllegalArgumentException("Unknown op: " + op);
};
}
}
All results: [-34, -14, -10, -10, 10]
How does the divide-and-conquer recursion work?
Scan the expression character by character. At each operator, treat it as the top-level operation of one grouping. Recursively compute all results of the left substring and all results of the right substring. Then combine every left result with every right result using the operator.
Expression: "2*3-4"
Split at '*' (index 1):
left = "2" -> [2]
right = "3-4" -> [-1, ...] (recurse)
Combine: 2 * (-1) = -2
Split at '-' (index 3):
left = "2*3" -> [6] (recurse)
right = "4" -> [4]
Combine: 6 - 4 = 2
Results: [-2, 2]
Why is memoization important?
The number of distinct groupings follows the Catalan number sequence. For n operators, there are C(n) groupings where C(1)=1, C(2)=2, C(3)=5, C(4)=14. Without memoization, overlapping sub-expressions are recomputed many times. Caching by substring key ensures each sub-expression is solved once.
// Without memo: exponential recomputation
// "2*3-4*5" splits at each operator, and sub-expressions overlap
// With memo: each unique substring computed once
static Map<String, List<Integer>> memo = new HashMap<>();
if (memo.containsKey(expr)) return memo.get(expr);
// ... compute ...
memo.put(expr, results);
How do you use BigDecimal for exact banking arithmetic?
In a banking context, use BigDecimal instead of int to keep all arithmetic exact and avoid floating-point errors. Replace +, -, * with add, subtract, multiply.
package com.bank.formula;
import java.math.BigDecimal;
import java.util.*;
public class DiffWaysBigDecimal {
static Map<String, List<BigDecimal>> memo = new HashMap<>();
static List<BigDecimal> diffWays(String expr) {
if (memo.containsKey(expr)) return memo.get(expr);
List<BigDecimal> results = new ArrayList<>();
for (int i = 0; i < expr.length(); i++) {
char c = expr.charAt(i);
if (c == '+' || c == '-' || c == '*') {
for (BigDecimal l : diffWays(expr.substring(0, i))) {
for (BigDecimal r : diffWays(expr.substring(i + 1))) {
results.add(applyOp(l, r, c));
}
}
}
}
if (results.isEmpty()) results.add(new BigDecimal(expr));
memo.put(expr, results);
return results;
}
static BigDecimal applyOp(BigDecimal a, BigDecimal b, char op) {
return switch (op) {
case '+' -> a.add(b);
case '-' -> a.subtract(b);
case '*' -> a.multiply(b);
default -> throw new IllegalArgumentException();
};
}
public static void main(String[] args) {
List<BigDecimal> results = diffWays("100*3-50*2");
Collections.sort(results);
System.out.println("Fee formula results: " + results);
}
}
Fee formula results: [-9700, -100, 100, 200, 500]
What is the time and space complexity?
The number of results for n operators is the Catalan number C(n), which grows as O(4^n / n^(3/2)). Memoization ensures each of the O(n^2) unique substrings is computed once, but the total number of results across all substrings is still exponential.
| Metric | Complexity |
|--------|------------|
| Unique substrings | O(n^2) |
| Results per expression | Catalan(operators) |
| Time with memo | O(n^2 * C(n)) roughly |
| Space | O(n^2 * C(n)) for memo |
What are the edge cases?
Edge cases include a single number (no operators), an expression with only one operator, and multi-digit numbers.
package com.bank.formula;
import java.util.List;
public class EdgeCases {
public static void main(String[] args) {
// Single number
System.out.println(DiffWaysToCompute.diffWaysToCompute("42")); // [42]
// One operator
System.out.println(DiffWaysToCompute.diffWaysToCompute("3+5")); // [8]
// Multi-digit numbers
System.out.println(DiffWaysToCompute.diffWaysToCompute("10+20")); // [30]
}
}
[42]
[8]
[30]
What are common mistakes?
The most common mistake is trying to use Integer.parseInt on the whole string before checking for operators, which fails for multi-operator expressions. The correct approach is to try splitting at every operator position first, and only parse as a number when no operator is found.
// WRONG: parse first, split later
int num = Integer.parseInt(expr); // throws for "2+3"
// CORRECT: split at operators; parse only if no operator found
for (int i = 0; i < expr.length(); i++) {
if (isOperator(expr.charAt(i))) {
// split and recurse
}
}
if (results.isEmpty()) {
results.add(Integer.parseInt(expr)); // safe: no operators
}
What should a senior engineer know?
- Catalan numbers. The growth rate matters: for 10 operators there are 16,796 groupings. For practical expressions this is fine, but for very long expressions the output itself is exponential.
- Division operator. Adding division requires handling division by zero. In a banking formula evaluator, division would use BigDecimal with a specified scale and rounding mode.
- Expression trees. Each grouping corresponds to a distinct binary expression tree. This problem enumerates all structurally distinct trees.
- Production formula engines. In production, formulas are parsed once into an AST, not re-evaluated by string splitting. The divide-and-conquer approach demonstrates the concept but is not the production implementation.
Visual Overview
Expression: "2 * 3 - 4"
Split at '*' (top-level):
┌─────┐ ┌─────────┐
│ 2 │ * │ 3 - 4 │
└─────┘ └─────────┘
[2] split at '-':
┌───┐ ┌───┐
│ 3 │ - │ 4 │
└───┘ └───┘
[3] [4]
Result: [3-4] = [-1]
Combine: 2 * (-1) = -2
Split at '-' (top-level):
┌─────────┐ ┌───┐
│ 2 * 3 │ - │ 4 │
└─────────┘ └───┘
split at '*': [4]
[2] * [3] = [6]
Combine: 6 - 4 = 2
All results: [-2, 2]
Key Takeaway
Evaluate Expression, also known as Different Ways to Add Parentheses, asks for every possible result from all ways of grouping an arithmetic expression. I solve it with divide and conquer: at every operator, I split the expression into left and right halves, recursively compute all results of each, and combine every left with every right using that operator. A substring with no operator is a plain number returning a single-element list.
I memoize results by substring key so overlapping sub-expressions are computed only once. Without memoization, the exponential growth of Catalan-number-many groupings would cause massive recomputation.
In a banking context at National Bank of India, I used this to explore the range of totals a fee formula could produce, because different groupings change the result and finance needed to see every possible outcome. I kept the arithmetic in BigDecimal to ensure exact results, which matters when the formula involves money.
The senior insight is that each grouping corresponds to a distinct binary expression tree, the count of which follows the Catalan sequence. For practical expressions with a handful of operators, the output is manageable, but for longer expressions the result set itself is exponential.
Remember one sentence: split at every operator, recurse on both sides, combine all left-right pairs, memoize by substring, and the result is every possible evaluation of the expression.
---