Basic Calculator IV

Hard Stack Stack Basics Original on LeetCode

Reported atMetaIntuit

Basic Calculator IV is a hard stack problem solved with the stack basics pattern. The best approach, optimal (recursive descent over merged polynomials), runs in O(M² · L) per multiplication time and O(M · L) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (expand without merging) up.

Problem

You are given an arithmetic expression built from non-negative integers, lowercase variable names, +, -, * and parentheses, with a single space between tokens (parentheses may sit right next to what they enclose). You also get two parallel lists: evalvars[i] has the known value evalints[i]. Every other variable stays symbolic.

Simplify the expression into a polynomial and return its terms as strings. A term is written as its coefficient followed by its variables, each prefixed by *, with the variables in each term sorted alphabetically (for example "-3*a*a*c"); the constant term is just the number (for example "12").

Order the terms by degree (number of variables, counted with repetition) from highest to lowest, and break ties by comparing the variable lists lexicographically. Leave out every term whose coefficient is 0; if nothing is left, return an empty list. * binds tighter than + and -, which are evaluated left to right.

Examples

Example 1

Input
expression = "x * 3 + y - x", evalvars = ["y"], evalints = [4]
Output
["2*x", "4"]
Why
y becomes 4, and 3x - x simplifies to 2x. The degree-1 term comes before the constant.

Example 2

Input
expression = "(p + 2) * (p - q)", evalvars = [], evalints = []
Output
["1*p*p", "-1*p*q", "2*p", "-2*q"]
Why
Expanding gives pp - pq + 2p - 2q. Degree-2 terms come first, ties broken by the variable list.

Example 3

Input
expression = "k - k + 7 * 0", evalvars = [], evalints = []
Output
[]
Why
Everything cancels to 0, and zero terms are never printed.

Constraints

  • 1 <= expression.length <= 250
  • expression contains lowercase letters, digits, +, -, *, (, ) and single spaces between tokens.
  • There is no unary minus, and the expression is always valid.
  • 0 <= evalvars.length <= 100, evalvars.length == evalints.length
  • 1 <= evalvars[i].length <= 20, -100 <= evalints[i] <= 100
  • Every coefficient met while simplifying fits in a 32-bit signed integer.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 16 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (expand without merging)O(2^n) in the worst caseO(2^n)
Optimal (recursive descent over merged polynomials)O(M² · L) per multiplicationO(M · L)

1Brute force (expand without merging)

TimeO(2^n) in the worst caseWithout merging, each product of two sums multiplies the number of stored terms, e.g. `(a + a) * (a + a) * ...`.
SpaceO(2^n)All unmerged terms are kept until the end.

Parse with the usual precedence rules, but keep every product term as its own entry in a list. Like terms are only merged once, at the very end. This is easy to reason about, but repeated products of sums make the list grow exponentially.

  1. Split the string into tokens: numbers, variable names, operators and parentheses.
  2. A factor becomes a one-term list: a constant, a substituted known variable, or (variable, coefficient 1).
  3. * builds the cross product of two lists, concatenating and sorting the variable names of each pair.
  4. +/- appends the right-hand list (negated for -).
  5. At the end, sum coefficients per variable list, drop zeros, sort by degree (descending) then by variable list, and format.
class Solution {
    static class Term {
        long coef;
        String key;
        Term(long coef, String key) { this.coef = coef; this.key = key; }
    }

    private List<String> tokens;
    private int pos;
    private Map<String, Integer> env;

    public List<String> basicCalculatorIV(String expression, String[] evalvars, int[] evalints) {
        env = new HashMap<>();
        for (int i = 0; i < evalvars.length; i++) env.put(evalvars[i], evalints[i]);
        tokens = new ArrayList<>();
        int i = 0, n = expression.length();
        while (i < n) {
            char c = expression.charAt(i);
            if (c == ' ') { i++; continue; }
            if (Character.isLetterOrDigit(c)) {
                int j = i;
                while (j < n && Character.isLetterOrDigit(expression.charAt(j))) j++;
                tokens.add(expression.substring(i, j));
                i = j;
            } else {
                tokens.add(String.valueOf(c));
                i++;
            }
        }
        pos = 0;
        Map<String, Long> poly = new HashMap<>();
        for (Term t : parseExpr()) poly.merge(t.key, t.coef, Long::sum);
        List<String> keys = new ArrayList<>();
        for (Map.Entry<String, Long> e : poly.entrySet()) if (e.getValue() != 0) keys.add(e.getKey());
        keys.sort((a, b) -> degree(a) != degree(b) ? degree(b) - degree(a) : a.compareTo(b));
        List<String> out = new ArrayList<>();
        for (String k : keys) out.add(k.isEmpty() ? String.valueOf(poly.get(k)) : poly.get(k) + "*" + k);
        return out;
    }

    private int degree(String key) {
        if (key.isEmpty()) return 0;
        int d = 1;
        for (char c : key.toCharArray()) if (c == '*') d++;
        return d;
    }

    private List<Term> parseExpr() {
        List<Term> res = parseTerm();
        while (pos < tokens.size() && (tokens.get(pos).equals("+") || tokens.get(pos).equals("-"))) {
            long sign = tokens.get(pos).equals("+") ? 1 : -1;
            pos++;
            for (Term t : parseTerm()) res.add(new Term(sign * t.coef, t.key));
        }
        return res;
    }

    private List<Term> parseTerm() {
        List<Term> res = parseFactor();
        while (pos < tokens.size() && tokens.get(pos).equals("*")) {
            pos++;
            List<Term> rhs = parseFactor();
            List<Term> prod = new ArrayList<>();
            for (Term x : res) {
                for (Term y : rhs) prod.add(new Term(x.coef * y.coef, combine(x.key, y.key)));
            }
            res = prod;
        }
        return res;
    }

    private List<Term> parseFactor() {
        String t = tokens.get(pos++);
        List<Term> res = new ArrayList<>();
        if (t.equals("(")) {
            res = parseExpr();
            pos++; // skip ')'
        } else if (Character.isDigit(t.charAt(0))) {
            res.add(new Term(Long.parseLong(t), ""));
        } else if (env.containsKey(t)) {
            res.add(new Term(env.get(t), ""));
        } else {
            res.add(new Term(1, t));
        }
        return res;
    }

    private String combine(String a, String b) {
        List<String> vars = new ArrayList<>();
        if (!a.isEmpty()) vars.addAll(Arrays.asList(a.split("\\*")));
        if (!b.isEmpty()) vars.addAll(Arrays.asList(b.split("\\*")));
        Collections.sort(vars);
        return String.join("*", vars);
    }
}

2Optimal (recursive descent over merged polynomials)

TimeO(M² · L) per multiplicationM is the number of distinct monomials in the two operands and L the cost of merging and sorting a key; merging keeps M small.
SpaceO(M · L)Each polynomial stores at most M keys of length up to L.

Same parser, but every sub-result is a polynomial map from a variable key (the sorted variable names joined by *, empty for the constant) to its coefficient. Like terms merge as soon as they appear, so the size of any intermediate result is bounded by the number of distinct monomials, not by the number of expansions.

  1. Tokenize, and put the known variables into a map from name to value.
  2. parseExpr: read a term, then while the next token is + or -, read another term and add (or subtract) its coefficients key by key.
  3. parseTerm: read a factor, then while the next token is *, multiply by the next factor: every pair of keys is combined into a sorted key and their coefficients multiply and accumulate.
  4. parseFactor: ( starts a nested expression; a number or known variable is a constant; an unknown variable is the key name with coefficient 1.
  5. Drop zero coefficients, sort keys by degree (descending) then lexicographically by variable list, and print coef*key (just coef for the constant).
class Solution {
    private List<String> tokens;
    private int pos;
    private Map<String, Integer> env;

    public List<String> basicCalculatorIV(String expression, String[] evalvars, int[] evalints) {
        env = new HashMap<>();
        for (int i = 0; i < evalvars.length; i++) env.put(evalvars[i], evalints[i]);
        tokens = new ArrayList<>();
        int i = 0, n = expression.length();
        while (i < n) {
            char c = expression.charAt(i);
            if (c == ' ') { i++; continue; }
            if (Character.isLetterOrDigit(c)) {
                int j = i;
                while (j < n && Character.isLetterOrDigit(expression.charAt(j))) j++;
                tokens.add(expression.substring(i, j));
                i = j;
            } else {
                tokens.add(String.valueOf(c));
                i++;
            }
        }
        pos = 0;
        Map<String, Long> poly = parseExpr();
        List<String> keys = new ArrayList<>();
        for (Map.Entry<String, Long> e : poly.entrySet()) if (e.getValue() != 0) keys.add(e.getKey());
        keys.sort((a, b) -> degree(a) != degree(b) ? degree(b) - degree(a) : a.compareTo(b));
        List<String> out = new ArrayList<>();
        for (String k : keys) out.add(k.isEmpty() ? String.valueOf(poly.get(k)) : poly.get(k) + "*" + k);
        return out;
    }

    private int degree(String key) {
        if (key.isEmpty()) return 0;
        int d = 1;
        for (char c : key.toCharArray()) if (c == '*') d++;
        return d;
    }

    private Map<String, Long> parseExpr() {
        Map<String, Long> res = parseTerm();
        while (pos < tokens.size() && (tokens.get(pos).equals("+") || tokens.get(pos).equals("-"))) {
            long sign = tokens.get(pos).equals("+") ? 1 : -1;
            pos++;
            for (Map.Entry<String, Long> e : parseTerm().entrySet()) {
                res.merge(e.getKey(), sign * e.getValue(), Long::sum);
            }
        }
        return res;
    }

    private Map<String, Long> parseTerm() {
        Map<String, Long> res = parseFactor();
        while (pos < tokens.size() && tokens.get(pos).equals("*")) {
            pos++;
            Map<String, Long> rhs = parseFactor();
            Map<String, Long> prod = new HashMap<>();
            for (Map.Entry<String, Long> x : res.entrySet()) {
                for (Map.Entry<String, Long> y : rhs.entrySet()) {
                    prod.merge(combine(x.getKey(), y.getKey()), x.getValue() * y.getValue(), Long::sum);
                }
            }
            res = prod;
        }
        return res;
    }

    private Map<String, Long> parseFactor() {
        String t = tokens.get(pos++);
        Map<String, Long> res = new HashMap<>();
        if (t.equals("(")) {
            res = parseExpr();
            pos++; // skip ')'
        } else if (Character.isDigit(t.charAt(0))) {
            res.put("", Long.parseLong(t));
        } else if (env.containsKey(t)) {
            res.put("", (long) env.get(t));
        } else {
            res.put(t, 1L);
        }
        return res;
    }

    private String combine(String a, String b) {
        List<String> vars = new ArrayList<>();
        if (!a.isEmpty()) vars.addAll(Arrays.asList(a.split("\\*")));
        if (!b.isEmpty()) vars.addAll(Arrays.asList(b.split("\\*")));
        Collections.sort(vars);
        return String.join("*", vars);
    }
}

Edge cases to test

  • All terms cancel, so the answer is an empty list
  • A variable is used with itself (a * a), so a variable repeats inside one term
  • Variables with names that are prefixes of each other, like a and ab
  • A known variable inside parentheses next to unknown ones
  • Nested parentheses and a multiplication that binds tighter than -

Hints

Hint 1

Represent every sub-expression as a polynomial: a map from a sorted list of variable names (the empty list for the constant) to a coefficient.

Hint 2

Adding polynomials adds coefficients key by key; multiplying pairs every term of one with every term of the other and merges the variable lists.

Hint 3

Parse with precedence: an expression is terms joined by +/-, a term is factors joined by *, and a factor is a number, a variable or a parenthesised expression.

FAQ

What is the best time complexity for Basic Calculator IV?

Optimal (recursive descent over merged polynomials) runs in O(M² · L) per multiplication time and O(M · L) extra space. M is the number of distinct monomials in the two operands and L the cost of merging and sorting a key; merging keeps M small.

Which pattern does Basic Calculator IV use?

It is a stack problem that uses the stack basics pattern. Other problems with the same pattern: Valid Parentheses, Baseball Game, Asteroid Collision.

Is there a brute force solution for Basic Calculator IV?

Yes. Brute force (expand without merging) takes O(2^n) in the worst case time and O(2^n) space. Parse with the usual precedence rules, but keep every product term as its own entry in a list.

Which edge cases should I test for Basic Calculator IV?

All terms cancel, so the answer is an empty list; A variable is used with itself (a a), so a variable repeats inside one term; Variables with names that are prefixes of each other, like a and ab; A known variable inside parentheses next to unknown ones; Nested parentheses and a multiplication that binds tighter than -.