Basic Calculator IV

HARD

Description

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 [-2³¹, 2³¹ - 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

Approaches

Checkout 2 different approaches to solve Basic Calculator IV. Click on different approaches to view the approach and algorithm in detail.

Recursive Descent with List-based Polynomial Representation

This approach tackles the problem by parsing the expression and performing polynomial arithmetic. It uses a straightforward, but inefficient, data structure to represent polynomials: a simple list of term objects. Each operation, like addition or multiplication, produces a new list of terms which must then be explicitly simplified by iterating through the list to find and combine terms with the same variables.

Algorithm

Represent a polynomial as a List<Term>, where Term is a class containing a coefficient and a list of variables.
Use a recursive descent parser to break down the expression according to operator precedence ((), then *, then +/-).
For addition and subtraction operations, concatenate the lists of terms from the two operand polynomials.
For multiplication, generate a new list of terms by taking the cross product of the terms from the two operand polynomials.
After each operation that modifies the list of terms (like addition or multiplication), call a simplify method.
The simplify method iterates through the list to find and combine like terms (terms with the same set of variables). This typically requires a nested loop, comparing each term with every other term.
Finally, sort the simplified list of terms from the final polynomial according to the specified output format and convert them to strings.

In this method, we define a Polynomial as a List<Term>, and a Term as an object holding a coefficient and a List<String> of variables. The parsing logic is handled by a recursive descent parser which correctly respects operator precedence.

When two polynomials are added, their term lists are simply concatenated. When they are multiplied, a new list is formed containing the product of every term from the first polynomial with every term from the second. The main drawback is that after these operations, the resulting list contains duplicate variable combinations (e.g., two separate terms for a*b).

To handle this, a simplify() function is called. This function has to go through the list and merge these like terms. A naive implementation would involve a nested loop: for each term, scan the rest of the list for terms with the same variables and combine them. This leads to a quadratic time complexity in the number of terms, which is highly inefficient, especially for expressions that generate many terms.

Complexity Analysis

Time Complexity: The time complexity is dominated by the `simplify` operation. If an intermediate polynomial has `T` terms, simplification takes `O(T^2 * D)`. Since multiplication of two polynomials with `T1` and `T2` terms can result in `T1 * T2` terms, the overall complexity can be very high, making it impractical for expressions that generate a large number of terms.Space Complexity: O(T_max * D), where `T_max` is the maximum number of terms in any intermediate polynomial before simplification, and `D` is the maximum degree. The space can be large as simplification is a separate, potentially deferred, step.

Pros and Cons

Pros:

The logic is conceptually simple, with a clear separation between generating terms and simplifying the result.

Cons:

The simplification step, which is required after most operations, is very inefficient. Combining like terms in a list of size T takes O(T^2 * D) time, where D is the maximum degree (cost to compare variable lists).
Generates many intermediate Term objects, potentially leading to higher memory usage and garbage collection overhead before simplification.

Code Solutions

Checking out 2 solutions in different languages for Basic Calculator IV. Click on different languages to view the code.

Video Solution

Watch the video walkthrough for Basic Calculator IV

Patterns:

MathRecursion

Data Structures:

Hash TableStringStack

Companies:

Intuit |Roblox |