LeetCode #770 — HARD

Basic Calculator IV

Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.

Solve on LeetCode
The Problem

Problem Statement

Given an expression such as expression = "e + 8 - a + 5" and an evaluation map such as {"e": 1} (given in terms of evalvars = ["e"] and evalints = [1]), return a list of tokens representing the simplified expression, such as ["-1*a","14"]

  • An expression alternates chunks and symbols, with a space separating each chunk and symbol.
  • A chunk is either an expression in parentheses, a variable, or a non-negative integer.
  • A variable is a string of lowercase letters (not including digits.) Note that variables can be multiple letters, and note that variables never have a leading coefficient or unary operator like "2x" or "-x".

Expressions are evaluated in the usual order: brackets first, then multiplication, then addition and subtraction.

  • For example, expression = "1 + 2 * 3" has an answer of ["7"].

The format of the output is as follows:

  • For each term of free variables with a non-zero coefficient, we write the free variables within a term in sorted order lexicographically.
    • For example, we would never write a term like "b*a*c", only "a*b*c".
  • Terms have degrees equal to the number of free variables being multiplied, counting multiplicity. We write the largest degree terms of our answer first, breaking ties by lexicographic order ignoring the leading coefficient of the term.
    • For example, "a*a*b*c" has degree 4.
  • The leading coefficient of the term is placed directly to the left with an asterisk separating it from the variables (if they exist.) A leading coefficient of 1 is still printed.
  • An example of a well-formatted answer is ["-2*a*a*a", "3*a*a*b", "3*b*b", "4*a", "5*c", "-6"].
  • Terms (including constant terms) with coefficient 0 are not included.
    • For example, an expression of "0" has an output of [].

Note: You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].

Example 1:

Input: expression = "e + 8 - a + 5", evalvars = ["e"], evalints = [1]
Output: ["-1*a","14"]

Example 2:

Input: expression = "e - 8 + temperature - pressure", evalvars = ["e", "temperature"], evalints = [1, 12]
Output: ["-1*pressure","5"]

Example 3:

Input: expression = "(e + 8) * (e - 8)", evalvars = [], evalints = []
Output: ["1*e*e","-64"]

Constraints:

  • 1 <= expression.length <= 250
  • expression consists of lowercase English letters, digits, '+', '-', '*', '(', ')', ' '.
  • expression does not contain any leading or trailing spaces.
  • All the tokens in expression are separated by a single space.
  • 0 <= evalvars.length <= 100
  • 1 <= evalvars[i].length <= 20
  • evalvars[i] consists of lowercase English letters.
  • evalints.length == evalvars.length
  • -100 <= evalints[i] <= 100
Patterns Used
📚Monotonic Stack→

Roadmap

  1. Brute Force Baseline
  2. Core Insight
  3. Algorithm Walkthrough
  4. Edge Cases
  5. Full Annotated Code
  6. Interactive Study Demo
  7. Complexity Analysis
Step 01

Brute Force Baseline

Problem summary: Given an expression such as expression = "e + 8 - a + 5" and an evaluation map such as {"e": 1} (given in terms of evalvars = ["e"] and evalints = [1]), return a list of tokens representing the simplified expression, such as ["-1*a","14"] An expression alternates chunks and symbols, with a space separating each chunk and symbol. A chunk is either an expression in parentheses, a variable, or a non-negative integer. A variable is a string of lowercase letters (not including digits.) Note that variables can be multiple letters, and note that variables never have a leading coefficient or unary operator like "2x" or "-x". Expressions are evaluated in the usual order: brackets first, then multiplication, then addition and subtraction. For example, expression = "1 + 2 * 3" has an answer of ["7"]. The format of the output is as follows: For each term of free variables with a non-zero

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Hash Map · Math · Stack

Example 1

"e + 8 - a + 5"
["e"]
[1]

Example 2

"e - 8 + temperature - pressure"
["e", "temperature"]
[1, 12]

Example 3

"(e + 8) * (e - 8)"
[]
[]

Related Problems

  • Parse Lisp Expression (parse-lisp-expression)
  • Basic Calculator III (basic-calculator-iii)
Step 02

Core Insight

What unlocks the optimal approach

  • One way is with a Polynomial class. For example, * `Poly:add(this, that)` returns the result of `this + that`. * `Poly:sub(this, that)` returns the result of `this - that`. * `Poly:mul(this, that)` returns the result of `this * that`. * `Poly:evaluate(this, evalmap)` returns the polynomial after replacing all free variables with constants as specified by `evalmap`. * `Poly:toList(this)` returns the polynomial in the correct output format. * `Solution::combine(left, right, symbol)` returns the result of applying the binary operator represented by `symbol` to `left` and `right`. * `Solution::make(expr)` makes a new `Poly` represented by either the constant or free variable specified by `expr`. * `Solution::parse(expr)` parses an expression into a new `Poly`.
Interview move: turn each hint into an invariant you can check after every iteration/recursion step.
Step 03

Algorithm Walkthrough

Iteration Checklist

  1. Define state (indices, window, stack, map, DP cell, or recursion frame).
  2. Apply one transition step and update the invariant.
  3. Record answer candidate when condition is met.
  4. Continue until all input is consumed.
Use the first example testcase as your mental trace to verify each transition.
Step 04

Edge Cases

Minimum Input
Single element / shortest valid input
Validate boundary behavior before entering the main loop or recursion.
Duplicates & Repeats
Repeated values / repeated states
Decide whether duplicates should be merged, skipped, or counted explicitly.
Extreme Constraints
Largest constraint values
Re-check complexity target against constraints to avoid time-limit issues.
Invalid / Corner Shape
Empty collections, zeros, or disconnected structures
Handle special-case structure before the core algorithm path.
Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #770: Basic Calculator IV
class Poly {
  public Poly add(Poly o) {
    for (final String term : o.terms.keySet())
      terms.merge(term, o.terms.get(term), Integer::sum);
    return this;
  }

  public Poly minus(Poly o) {
    for (final String term : o.terms.keySet())
      terms.merge(term, -o.terms.get(term), Integer::sum);
    return this;
  }

  public Poly mult(Poly o) {
    Poly res = new Poly();
    for (final String a : terms.keySet())
      for (final String b : o.terms.keySet())
        res.terms.merge(merge(a, b), terms.get(a) * o.terms.get(b), Integer::sum);
    return res;
  }

  // @Override
  // Public String toString() {
  //   StringBuilder sb = new StringBuilder();
  //   sb.append("{");
  //   for (final String term : terms.keySet())
  //     sb.append(term).append(": ").append(terms.get(term)).append(", ");
  //   sb.append("}");
  //   return sb.toString();
  // }

  public List<String> toList() {
    List<String> res = new ArrayList<>();
    List<String> keys = new ArrayList<>(terms.keySet());
    Collections.sort(keys, new Comparator<String>() {
      @Override
      public int compare(final String a, final String b) {
        // the minimum degree is the last
        if (a.equals("1"))
          return 1;
        if (b.equals("1"))
          return -1;
        String[] as = a.split("\\*");
        String[] bs = b.split("\\*");
        // the maximum degree is the first
        // Break ties by their lexicographic orders.
        return as.length == bs.length ? a.compareTo(b) : bs.length - as.length;
      }
    });
    for (final String key : keys)
      if (terms.get(key) != 0)
        res.add(concat(key));
    return res;
  }

  public Poly() {}
  public Poly(final String term, int coef) {
    terms.put(term, coef);
  }

  private Map<String, Integer> terms = new HashMap<>();

  // e.g. merge("a*b", "a*c") -> "a*a*b*c"
  private static String merge(final String a, final String b) {
    if (a.equals("1"))
      return b;
    if (b.equals("1"))
      return a;
    StringBuilder sb = new StringBuilder();
    String[] A = a.split("\\*");
    String[] B = b.split("\\*");
    int i = 0; // A's index
    int j = 0; // B's index
    while (i < A.length && j < B.length)
      if (A[i].compareTo(B[j]) < 0)
        sb.append("*").append(A[i++]);
      else
        sb.append("*").append(B[j++]);
    while (i < A.length)
      sb.append("*").append(A[i++]);
    while (j < B.length)
      sb.append("*").append(B[j++]);
    return sb.substring(1).toString();
  }

  private String concat(final String term) {
    if (term.equals("1"))
      return String.valueOf(terms.get(term));
    return new StringBuilder().append(terms.get(term)).append('*').append(term).toString();
  }
}

class Solution {
  public List<String> basicCalculatorIV(String expression, String[] evalvars, int[] evalints) {
    List<String> tokens = getTokens(expression);
    Map<String, Integer> evalMap = new HashMap<>();

    for (int i = 0; i < evalvars.length; ++i)
      evalMap.put(evalvars[i], evalints[i]);

    for (int i = 0; i < tokens.size(); ++i)
      if (evalMap.containsKey(tokens.get(i)))
        tokens.set(i, String.valueOf(evalMap.get(tokens.get(i))));

    List<String> postfix = infixToPostfix(tokens);
    return evaluate(postfix).toList();
  }

  private List<String> getTokens(final String s) {
    List<String> tokens = new ArrayList<>();
    int i = 0;
    for (int j = 0; j < s.length(); ++j)
      if (s.charAt(j) == ' ') {
        if (i < j)
          tokens.add(s.substring(i, j));
        i = j + 1;
      } else if ("()+-*".contains(s.substring(j, j + 1))) {
        if (i < j)
          tokens.add(s.substring(i, j));
        tokens.add(s.substring(j, j + 1));
        i = j + 1;
      }
    if (i < s.length())
      tokens.add(s.substring(i));
    return tokens;
  }

  private boolean isOperator(final String token) {
    return token.equals("+") || token.equals("-") || token.equals("*");
  }

  private boolean precedes(final String prevOp, final String currOp) {
    if (prevOp.equals("("))
      return false;
    return prevOp.equals("*") || currOp.equals("+") || currOp.equals("-");
  }

  private List<String> infixToPostfix(List<String> tokens) {
    List<String> postfix = new ArrayList<>();
    Deque<String> ops = new ArrayDeque<>();

    for (final String token : tokens)
      if (token.equals("(")) {
        ops.push(token);
      } else if (token.equals(")")) {
        while (!ops.peek().equals("("))
          postfix.add(ops.pop());
        ops.pop();
      } else if (isOperator(token)) {
        while (!ops.isEmpty() && precedes(ops.peek(), token))
          postfix.add(ops.pop());
        ops.push(token);
      } else { // isOperand(token)
        postfix.add(token);
      }

    while (!ops.isEmpty())
      postfix.add(ops.pop());

    return postfix;
  }

  private Poly evaluate(List<String> postfix) {
    LinkedList<Poly> polys = new LinkedList<>();
    for (final String token : postfix)
      if (isOperator(token)) {
        final Poly b = polys.removeLast();
        final Poly a = polys.removeLast();
        if (token.equals("+"))
          polys.add(a.add(b));
        else if (token.equals("-"))
          polys.add(a.minus(b));
        else // token == "*"
          polys.add(a.mult(b));
      } else if (token.charAt(0) == '-' || token.chars().allMatch(c -> Character.isDigit(c))) {
        polys.add(new Poly("1", Integer.parseInt(token)));
      } else {
        polys.add(new Poly(token, 1));
      }
    return polys.getFirst();
  }
}
Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Press Step or Run All to begin.
Step 07

Complexity Analysis

Time
O(n)
Space
O(n)

Approach Breakdown

BRUTE FORCE
O(n²) time
O(1) space

For each element, scan left (or right) to find the next greater/smaller element. The inner scan can visit up to n elements per outer iteration, giving O(n²) total comparisons. No extra space needed beyond loop variables.

MONOTONIC STACK
O(n) time
O(n) space

Each element is pushed onto the stack at most once and popped at most once, giving 2n total operations = O(n). The stack itself holds at most n elements in the worst case. The key insight: amortized O(1) per element despite the inner while-loop.

Shortcut: Each element pushed once + popped once → O(n) amortized. The inner while-loop does not make it O(n²).
Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Mutating counts without cleanup

Wrong move: Zero-count keys stay in map and break distinct/count constraints.

Usually fails on: Window/map size checks are consistently off by one.

Fix: Delete keys when count reaches zero.

Overflow in intermediate arithmetic

Wrong move: Temporary multiplications exceed integer bounds.

Usually fails on: Large inputs wrap around unexpectedly.

Fix: Use wider types, modular arithmetic, or rearranged operations.

Breaking monotonic invariant

Wrong move: Pushing without popping stale elements invalidates next-greater/next-smaller logic.

Usually fails on: Indices point to blocked elements and outputs shift.

Fix: Pop while invariant is violated before pushing current element.

Related Problems
#2019The Score of Students Solving Math Expressionhard→#13Roman to Integereasy→#149Max Points on a Linehard→#150Evaluate Reverse Polish Notationmedium→#166Fraction to Recurring Decimalmedium→