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"]
"2x" or "-x".Expressions are evaluated in the usual order: brackets first, then multiplication, then addition and subtraction.
expression = "1 + 2 * 3" has an answer of ["7"].The format of the output is as follows:
"b*a*c", only "a*b*c"."a*a*b*c" has degree 4.["-2*a*a*a", "3*a*a*b", "3*b*b", "4*a", "5*c", "-6"].0 are not included.
"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 <= 250expression consists of lowercase English letters, digits, '+', '-', '*', '(', ')', ' '.expression does not contain any leading or trailing spaces.expression are separated by a single space.0 <= evalvars.length <= 1001 <= evalvars[i].length <= 20evalvars[i] consists of lowercase English letters.evalints.length == evalvars.length-100 <= evalints[i] <= 100Problem Overview: You are given an algebraic expression containing integers, variables, addition, subtraction, multiplication, and parentheses. Some variables have known values. The goal is to evaluate the expression, substitute known variables, and return the simplified polynomial sorted by degree and lexicographic order.
Approach 1: Stack-Based Expression Evaluation (O(n * t log t) time, O(t) space)
This approach parses the expression from left to right and evaluates it using stacks for operands and operators. Each operand is represented as a polynomial map: {monomial -> coefficient}, where the monomial is a sorted tuple of variables. When encountering numbers or variables, you create a polynomial term; if the variable has a value in the evaluation map, substitute it immediately. Operators such as +, -, and * combine polynomial maps by merging coefficients or performing pairwise multiplication of terms. Parentheses push and pop evaluation contexts from the stack. After processing the full expression, remaining terms are sorted by degree and lexicographic order. This method mirrors how calculators process expressions while extending operands to polynomial structures.
Approach 2: Recursive Evaluation with Operator Precedence (O(n * t log t) time, O(t) space)
This method builds a recursive parser that respects operator precedence and parentheses. The expression is split into additive segments, while multiplication is handled within each segment. Each recursive call processes a substring and returns a polynomial map representing its value. Variables are either substituted using the provided values or kept symbolically. Polynomial addition merges coefficient maps, while multiplication creates new monomials by concatenating and sorting variables. Using recursion naturally handles nested parentheses and keeps the parsing logic clean. Internally the polynomial representation relies heavily on a hash table for fast coefficient aggregation and often uses recursion to manage nested expressions.
Recommended for interviews: The recursive precedence parser is usually preferred because it clearly separates parsing logic from polynomial operations and handles nested expressions cleanly. The stack-based evaluator still demonstrates strong understanding of expression parsing and data structures. Interviewers mainly care about how you represent polynomials, combine terms during multiplication, and maintain correct ordering in the final result.
This approach uses a stack for handling tokens in the expression and evaluates them based on operator precedence and the values from the evaluation map.
The solution involves a stack data structure to parse and process the expression. It first builds an evaluation map for easy look-up of variable values. The main function parse goes through each character of expression, handling numbers, variables, and operators, maintaining the current total in the stack. Parentheses are handled using recursion, and the final result returned is built by summing up the stack's contents.
Python
JavaScript
Time Complexity: O(n), where n is the length of the expression, as we process each character at most a few times due to stack operations.
Space Complexity: O(n), owing to the stack used for parsing nested expressions.
This solution recursively parses and evaluates expressions according to the priority of operators. It evaluates elements within parentheses first and processes operations by precedence level.
This implementation recursively evaluates parts of the expression within parentheses, adhering to operator precedence. It utilizes a stack for handling addition/subtraction and directly processes multiplication. Similar variable evaluation as in previous solutions applies here, with recursion used for handling '(' and ')' correctly.
Time Complexity: O(n), where n is the length of the input expression considering the recursive evaluation process simplifies multiple sub-expressions.
Space Complexity: O(n) due to recursion and stack usage for sub-expressions.
| Approach | Complexity |
|---|---|
| Stack-Based Expression Evaluation | Time Complexity: O(n), where n is the length of the expression, as we process each character at most a few times due to stack operations. Space Complexity: O(n), owing to the stack used for parsing nested expressions. |
| Recursive Evaluation with Operator Precedence | Time Complexity: O(n), where n is the length of the input expression considering the recursive evaluation process simplifies multiple sub-expressions. Space Complexity: O(n) due to recursion and stack usage for sub-expressions. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack-Based Expression Evaluation | O(n * t log t) | O(t) | Good when implementing a calculator-style parser with explicit operator stacks |
| Recursive Evaluation with Operator Precedence | O(n * t log t) | O(t) | Preferred for clean handling of parentheses and precedence in symbolic expressions |
Basic Calculator IV Leetcode Problem Intuition Discussion. • Anish De • 495 views views
Watch 4 more video solutions →Practice Basic Calculator IV with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor