LeetCodee

770. Basic Calculator IV

Jump to Solution: Python Java C++ JavaScript C#

Problem 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 strings representing all possible ways to group the numbers and variables to evaluate the expression.

Each answer should be formatted as a string with the same number of terms as the original expression, with each term being a single variable or a single number.

Examples:

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"]

Constraints:

  • 1 ≤ expression.length ≤ 250
  • expression consists of lowercase English letters, digits, '+', '-', '*', '(', ')', ' ' (spaces)
  • 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

Python Solution

class Solution:
    def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:
        # Create evaluation map
        eval_map = dict(zip(evalvars, evalints))
        
        def evaluate(expr):
            if not expr:
                return {}
            if expr[0] != '(':
                # Handle single term
                if expr[0].isdigit():
                    return {'': int(expr)}
                if expr[0].isalpha():
                    return {expr: 1}
                return {}
            
            # Find matching parenthesis
            count = 1
            i = 1
            while i < len(expr) and count > 0:
                if expr[i] == '(':
                    count += 1
                elif expr[i] == ')':
                    count -= 1
                i += 1
            
            # Evaluate inner expression
            inner = evaluate(expr[1:i-1])
            if i == len(expr):
                return inner
            
            # Handle operator
            op = expr[i]
            rest = evaluate(expr[i+1:])
            
            if op == '+':
                return add(inner, rest)
            elif op == '-':
                return subtract(inner, rest)
            else:
                return multiply(inner, rest)
        
        def add(d1, d2):
            result = d1.copy()
            for k, v in d2.items():
                result[k] = result.get(k, 0) + v
            return result
        
        def subtract(d1, d2):
            result = d1.copy()
            for k, v in d2.items():
                result[k] = result.get(k, 0) - v
            return result
        
        def multiply(d1, d2):
            result = {}
            for k1, v1 in d1.items():
                for k2, v2 in d2.items():
                    k = multiply_terms(k1, k2)
                    result[k] = result.get(k, 0) + v1 * v2
            return result
        
        def multiply_terms(t1, t2):
            if not t1:
                return t2
            if not t2:
                return t1
            terms = sorted((t1 + '*' + t2).split('*'))
            return '*'.join(terms)
        
        # Evaluate expression
        result = evaluate(expression)
        
        # Format result
        formatted = []
        for term in sorted(result.keys(), key=lambda x: (-len(x.split('*')), x)):
            if result[term] != 0:
                if not term:
                    formatted.append(str(result[term]))
                else:
                    formatted.append(f"{result[term]}*{term}")
        
        return formatted

Implementation Notes:

  • Uses recursive descent parsing to evaluate the expression
  • Maintains a dictionary to track terms and their coefficients
  • Handles addition, subtraction, and multiplication of terms
  • Time complexity: O(n^2) where n is length of expression
  • Space complexity: O(n) for storing intermediate results

Java Solution

class Solution {
    public List basicCalculatorIV(String expression, String[] evalvars, int[] evalints) {
        // Create evaluation map
        Map evalMap = new HashMap<>();
        for (int i = 0; i < evalvars.length; i++) {
            evalMap.put(evalvars[i], evalints[i]);
        }
        
        // Parse and evaluate expression
        Map result = evaluate(expression, evalMap);
        
        // Format result
        List formatted = new ArrayList<>();
        for (Map.Entry entry : result.entrySet()) {
            if (entry.getValue() != 0) {
                String term = entry.getKey();
                if (term.isEmpty()) {
                    formatted.add(String.valueOf(entry.getValue()));
                } else {
                    formatted.add(entry.getValue() + "*" + term);
                }
            }
        }
        
        // Sort by number of variables (descending) and lexicographically
        Collections.sort(formatted, (a, b) -> {
            int countA = a.split("\\*").length;
            int countB = b.split("\\*").length;
            if (countA != countB) {
                return countB - countA;
            }
            return a.compareTo(b);
        });
        
        return formatted;
    }
    
    private Map evaluate(String expr, Map evalMap) {
        Map result = new HashMap<>();
        if (expr == null || expr.isEmpty()) {
            return result;
        }
        
        // Handle single term
        if (!expr.contains("(")) {
            if (Character.isDigit(expr.charAt(0))) {
                result.put("", Integer.parseInt(expr));
            } else if (Character.isLetter(expr.charAt(0))) {
                result.put(expr, 1);
            }
            return result;
        }
        
        // Find matching parenthesis
        int i = 0;
        while (i < expr.length() && expr.charAt(i) != '(') {
            i++;
        }
        
        int j = i + 1;
        int count = 1;
        while (j < expr.length() && count > 0) {
            if (expr.charAt(j) == '(') {
                count++;
            } else if (expr.charAt(j) == ')') {
                count--;
            }
            j++;
        }
        
        // Evaluate inner expression
        Map inner = evaluate(expr.substring(i + 1, j - 1), evalMap);
        
        // Handle operator
        if (j < expr.length()) {
            char op = expr.charAt(j);
            Map rest = evaluate(expr.substring(j + 1), evalMap);
            
            if (op == '+') {
                result = add(inner, rest);
            } else if (op == '-') {
                result = subtract(inner, rest);
            } else if (op == '*') {
                result = multiply(inner, rest);
            }
        } else {
            result = inner;
        }
        
        return result;
    }
    
    private Map add(Map d1, Map d2) {
        Map result = new HashMap<>(d1);
        for (Map.Entry entry : d2.entrySet()) {
            result.merge(entry.getKey(), entry.getValue(), Integer::sum);
        }
        return result;
    }
    
    private Map subtract(Map d1, Map d2) {
        Map result = new HashMap<>(d1);
        for (Map.Entry entry : d2.entrySet()) {
            result.merge(entry.getKey(), -entry.getValue(), Integer::sum);
        }
        return result;
    }
    
    private Map multiply(Map d1, Map d2) {
        Map result = new HashMap<>();
        for (Map.Entry e1 : d1.entrySet()) {
            for (Map.Entry e2 : d2.entrySet()) {
                String term = multiplyTerms(e1.getKey(), e2.getKey());
                result.merge(term, e1.getValue() * e2.getValue(), Integer::sum);
            }
        }
        return result;
    }
    
    private String multiplyTerms(String t1, String t2) {
        if (t1.isEmpty()) return t2;
        if (t2.isEmpty()) return t1;
        String[] terms = (t1 + "*" + t2).split("\\*");
        Arrays.sort(terms);
        return String.join("*", terms);
    }
}

C++ Solution

class Solution {
public:
    vector basicCalculatorIV(string expression, vector& evalvars, vector& evalints) {
        // Create evaluation map
        unordered_map evalMap;
        for (int i = 0; i < evalvars.size(); i++) {
            evalMap[evalvars[i]] = evalints[i];
        }
        
        // Parse and evaluate expression
        unordered_map result = evaluate(expression, evalMap);
        
        // Format result
        vector formatted;
        for (const auto& entry : result) {
            if (entry.second != 0) {
                string term = entry.first;
                if (term.empty()) {
                    formatted.push_back(to_string(entry.second));
                } else {
                    formatted.push_back(to_string(entry.second) + "*" + term);
                }
            }
        }
        
        // Sort by number of variables (descending) and lexicographically
        sort(formatted.begin(), formatted.end(), [](const string& a, const string& b) {
            int countA = count(a.begin(), a.end(), '*') + 1;
            int countB = count(b.begin(), b.end(), '*') + 1;
            if (countA != countB) {
                return countA > countB;
            }
            return a < b;
        });
        
        return formatted;
    }
    
private:
    unordered_map evaluate(const string& expr, const unordered_map& evalMap) {
        unordered_map result;
        if (expr.empty()) {
            return result;
        }
        
        // Handle single term
        if (expr.find('(') == string::npos) {
            if (isdigit(expr[0])) {
                result[""] = stoi(expr);
            } else if (isalpha(expr[0])) {
                result[expr] = 1;
            }
            return result;
        }
        
        // Find matching parenthesis
        int i = 0;
        while (i < expr.length() && expr[i] != '(') {
            i++;
        }
        
        int j = i + 1;
        int count = 1;
        while (j < expr.length() && count > 0) {
            if (expr[j] == '(') {
                count++;
            } else if (expr[j] == ')') {
                count--;
            }
            j++;
        }
        
        // Evaluate inner expression
        unordered_map inner = evaluate(expr.substr(i + 1, j - i - 2), evalMap);
        
        // Handle operator
        if (j < expr.length()) {
            char op = expr[j];
            unordered_map rest = evaluate(expr.substr(j + 1), evalMap);
            
            if (op == '+') {
                result = add(inner, rest);
            } else if (op == '-') {
                result = subtract(inner, rest);
            } else if (op == '*') {
                result = multiply(inner, rest);
            }
        } else {
            result = inner;
        }
        
        return result;
    }
    
    unordered_map add(const unordered_map& d1, const unordered_map& d2) {
        unordered_map result = d1;
        for (const auto& entry : d2) {
            result[entry.first] += entry.second;
        }
        return result;
    }
    
    unordered_map subtract(const unordered_map& d1, const unordered_map& d2) {
        unordered_map result = d1;
        for (const auto& entry : d2) {
            result[entry.first] -= entry.second;
        }
        return result;
    }
    
    unordered_map multiply(const unordered_map& d1, const unordered_map& d2) {
        unordered_map result;
        for (const auto& e1 : d1) {
            for (const auto& e2 : d2) {
                string term = multiplyTerms(e1.first, e2.first);
                result[term] += e1.second * e2.second;
            }
        }
        return result;
    }
    
    string multiplyTerms(const string& t1, const string& t2) {
        if (t1.empty()) return t2;
        if (t2.empty()) return t1;
        vector terms;
        string term;
        istringstream iss(t1 + "*" + t2);
        while (getline(iss, term, '*')) {
            terms.push_back(term);
        }
        sort(terms.begin(), terms.end());
        string result;
        for (int i = 0; i < terms.size(); i++) {
            if (i > 0) result += "*";
            result += terms[i];
        }
        return result;
    }
};

JavaScript Solution

function basicCalculatorIV(expression, evalvars, evalints) {
    // Create evaluation map
    const evalMap = new Map();
    for (let i = 0; i < evalvars.length; i++) {
        evalMap.set(evalvars[i], evalints[i]);
    }
    
    function evaluate(expr) {
        const result = new Map();
        if (!expr) {
            return result;
        }
        
        // Handle single term
        if (!expr.includes('(')) {
            if (/^\d+$/.test(expr)) {
                result.set('', parseInt(expr));
            } else if (/^[a-z]+$/.test(expr)) {
                result.set(expr, 1);
            }
            return result;
        }
        
        // Find matching parenthesis
        let i = 0;
        while (i < expr.length && expr[i] !== '(') {
            i++;
        }
        
        let j = i + 1;
        let count = 1;
        while (j < expr.length && count > 0) {
            if (expr[j] === '(') {
                count++;
            } else if (expr[j] === ')') {
                count--;
            }
            j++;
        }
        
        // Evaluate inner expression
        const inner = evaluate(expr.substring(i + 1, j - 1));
        
        // Handle operator
        if (j < expr.length) {
            const op = expr[j];
            const rest = evaluate(expr.substring(j + 1));
            
            if (op === '+') {
                return add(inner, rest);
            } else if (op === '-') {
                return subtract(inner, rest);
            } else if (op === '*') {
                return multiply(inner, rest);
            }
        }
        
        return inner;
    }
    
    function add(d1, d2) {
        const result = new Map(d1);
        for (const [k, v] of d2) {
            result.set(k, (result.get(k) || 0) + v);
        }
        return result;
    }
    
    function subtract(d1, d2) {
        const result = new Map(d1);
        for (const [k, v] of d2) {
            result.set(k, (result.get(k) || 0) - v);
        }
        return result;
    }
    
    function multiply(d1, d2) {
        const result = new Map();
        for (const [k1, v1] of d1) {
            for (const [k2, v2] of d2) {
                const term = multiplyTerms(k1, k2);
                result.set(term, (result.get(term) || 0) + v1 * v2);
            }
        }
        return result;
    }
    
    function multiplyTerms(t1, t2) {
        if (!t1) return t2;
        if (!t2) return t1;
        const terms = (t1 + '*' + t2).split('*').sort();
        return terms.join('*');
    }
    
    // Evaluate expression
    const result = evaluate(expression);
    
    // Format result
    const formatted = [];
    for (const [term, coeff] of result) {
        if (coeff !== 0) {
            if (!term) {
                formatted.push(coeff.toString());
            } else {
                formatted.push(`${coeff}*${term}`);
            }
        }
    }
    
    // Sort by number of variables (descending) and lexicographically
    formatted.sort((a, b) => {
        const countA = (a.match(/\*/g) || []).length + 1;
        const countB = (b.match(/\*/g) || []).length + 1;
        if (countA !== countB) {
            return countB - countA;
        }
        return a.localeCompare(b);
    });
    
    return formatted;
}

C# Solution

public class Solution {
    public IList BasicCalculatorIV(string expression, string[] evalvars, int[] evalints) {
        // Create evaluation map
        var evalMap = new Dictionary();
        for (int i = 0; i < evalvars.Length; i++) {
            evalMap[evalvars[i]] = evalints[i];
        }
        
        // Parse and evaluate expression
        var result = Evaluate(expression, evalMap);
        
        // Format result
        var formatted = new List();
        foreach (var entry in result) {
            if (entry.Value != 0) {
                if (string.IsNullOrEmpty(entry.Key)) {
                    formatted.Add(entry.Value.ToString());
                } else {
                    formatted.Add($"{entry.Value}*{entry.Key}");
                }
            }
        }
        
        // Sort by number of variables (descending) and lexicographically
        formatted.Sort((a, b) => {
            int countA = a.Count(c => c == '*') + 1;
            int countB = b.Count(c => c == '*') + 1;
            if (countA != countB) {
                return countB - countA;
            }
            return string.Compare(a, b);
        });
        
        return formatted;
    }
    
    private Dictionary Evaluate(string expr, Dictionary evalMap) {
        var result = new Dictionary();
        if (string.IsNullOrEmpty(expr)) {
            return result;
        }
        
        // Handle single term
        if (!expr.Contains("(")) {
            if (int.TryParse(expr, out int num)) {
                result[""] = num;
            } else if (expr.All(char.IsLetter)) {
                result[expr] = 1;
            }
            return result;
        }
        
        // Find matching parenthesis
        int i = 0;
        while (i < expr.Length && expr[i] != '(') {
            i++;
        }
        
        int j = i + 1;
        int count = 1;
        while (j < expr.Length && count > 0) {
            if (expr[j] == '(') {
                count++;
            } else if (expr[j] == ')') {
                count--;
            }
            j++;
        }
        
        // Evaluate inner expression
        var inner = Evaluate(expr.Substring(i + 1, j - i - 2), evalMap);
        
        // Handle operator
        if (j < expr.Length) {
            char op = expr[j];
            var rest = Evaluate(expr.Substring(j + 1), evalMap);
            
            if (op == '+') {
                result = Add(inner, rest);
            } else if (op == '-') {
                result = Subtract(inner, rest);
            } else if (op == '*') {
                result = Multiply(inner, rest);
            }
        } else {
            result = inner;
        }
        
        return result;
    }
    
    private Dictionary Add(Dictionary d1, Dictionary d2) {
        var result = new Dictionary(d1);
        foreach (var entry in d2) {
            if (result.ContainsKey(entry.Key)) {
                result[entry.Key] += entry.Value;
            } else {
                result[entry.Key] = entry.Value;
            }
        }
        return result;
    }
    
    private Dictionary Subtract(Dictionary d1, Dictionary d2) {
        var result = new Dictionary(d1);
        foreach (var entry in d2) {
            if (result.ContainsKey(entry.Key)) {
                result[entry.Key] -= entry.Value;
            } else {
                result[entry.Key] = -entry.Value;
            }
        }
        return result;
    }
    
    private Dictionary Multiply(Dictionary d1, Dictionary d2) {
        var result = new Dictionary();
        foreach (var e1 in d1) {
            foreach (var e2 in d2) {
                string term = MultiplyTerms(e1.Key, e2.Key);
                if (result.ContainsKey(term)) {
                    result[term] += e1.Value * e2.Value;
                } else {
                    result[term] = e1.Value * e2.Value;
                }
            }
        }
        return result;
    }
    
    private string MultiplyTerms(string t1, string t2) {
        if (string.IsNullOrEmpty(t1)) return t2;
        if (string.IsNullOrEmpty(t2)) return t1;
        var terms = (t1 + "*" + t2).Split('*').OrderBy(t => t).ToArray();
        return string.Join("*", terms);
    }
}

Implementation Notes:

  • Uses recursive descent parsing to evaluate the expression
  • Maintains a dictionary to track terms and their coefficients
  • Handles addition, subtraction, and multiplication of terms
  • Time complexity: O(n^2) where n is length of expression
  • Space complexity: O(n) for storing intermediate results