Problem

You are given an algebraic expression in a string format and a map that gives the values to some of the variables in the expression. Your task is to simplify the expression by substituting the variables with their values and performing the algebraic operations.

The expression only contains lowercase alphabet variables, integers, addition, subtraction, and multiplication operations, and parentheses. It's guaranteed that there are spaces between different parts of the expression. The result should be presented as a list of strings where each string is a term in the simplified expression.

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

Here, the value of variable e is given as 1. When substituted we get "1 + 8 - a + 5". This simplifies to "14 - a" which is represented as two terms in the result, "-1*a" and "14".

Approach

The key steps in the solution are as follows.

1. Tokenize the expression. This involves breaking the expression into smaller units such as variables, integers, and operations.

2. Convert the infix expression to postfix for easier evaluation. This is achieved using a Stack. The infix to postfix conversion is based on the precedence of the operators where multiplication comes before addition and subtraction.

3. Evaluate the postfix expression. Every operand becomes a polynomial, stored as a map from a term key to its coefficient. A number 7 becomes {"": 7} (the empty key is the constant term), a variable with a given value becomes a constant in the same way, and any other variable a becomes {"a": 1}. Addition and subtraction merge two maps and add or subtract matching coefficients. Multiplication multiplies every term of the left polynomial by every term of the right one; the variable lists of the two terms are concatenated and sorted, so b*a and a*b produce the same key.

4. Simplify the terms and represent them in the required format. Terms whose coefficient is 0 are dropped. The remaining terms are sorted by degree (number of variable factors) from highest to lowest, and terms of equal degree are sorted lexicographically by their variable list. Each term is printed as coefficient*var1*var2..., and the constant term is printed as just the number.

Example

Let's see an example for a better understanding.

Input: expression = "a * b * c + b * a * c * 4", evalvars = [], evalints = []

In this case, we have an expression with multiplication and addition operations. Since there are no evalvars, we aren't substituting any variables.

The expression can still be simplified by combining like terms. The product "b * a * c" has its variables sorted into the key a*b*c, the same key as the first product. The coefficients 1 and 4 are added, giving "5 * a * b * c".

The final output is ["5ab*c"].

Python Solution

Copy
from typing import List


class Solution:
    def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:
        values = dict(zip(evalvars, evalints))

        # A polynomial is a dict: sorted tuple of variable names -> coefficient.
        # The empty tuple () holds the constant term.
        def add(p, q, sign):
            res = dict(p)
            for key, coef in q.items():
                res[key] = res.get(key, 0) + sign * coef
            return res

        def multiply(p, q):
            res = {}
            for k1, c1 in p.items():
                for k2, c2 in q.items():
                    key = tuple(sorted(k1 + k2))
                    res[key] = res.get(key, 0) + c1 * c2
            return res

        # Step 1: tokenize (parentheses may touch their neighbors)
        tokens = expression.replace('(', ' ( ').replace(')', ' ) ').split()

        # Step 2: convert infix to postfix (shunting-yard)
        precedence = {'+': 1, '-': 1, '*': 2}
        postfix, ops = [], []
        for token in tokens:
            if token == '(':
                ops.append(token)
            elif token == ')':
                while ops[-1] != '(':
                    postfix.append(ops.pop())
                ops.pop()
            elif token in precedence:
                while ops and ops[-1] != '(' and precedence[ops[-1]] >= precedence[token]:
                    postfix.append(ops.pop())
                ops.append(token)
            else:
                postfix.append(token)
        while ops:
            postfix.append(ops.pop())

        # Step 3: evaluate the postfix expression on polynomials
        stack = []
        for token in postfix:
            if token in precedence:
                right = stack.pop()
                left = stack.pop()
                if token == '*':
                    stack.append(multiply(left, right))
                else:
                    stack.append(add(left, right, 1 if token == '+' else -1))
            elif token.isdigit():
                stack.append({(): int(token)})
            elif token in values:
                stack.append({(): values[token]})
            else:
                stack.append({(token,): 1})
        poly = stack[-1]

        # Step 4: drop zero terms, sort by degree (desc) then lexicographically
        keys = sorted((k for k, c in poly.items() if c != 0), key=lambda k: (-len(k), k))
        return [str(poly[k]) + ''.join('*' + v for v in k) for k in keys]

Java Solution

Copy
import java.util.*;

class Solution {
    public List<String> basicCalculatorIV(String expression, String[] evalvars, int[] evalints) {
        Map<String, Integer> values = new HashMap<>();
        for (int i = 0; i < evalvars.length; i++) {
            values.put(evalvars[i], evalints[i]);
        }

        // Step 1: tokenize (parentheses may touch their neighbors)
        String[] tokens = expression.replace("(", " ( ").replace(")", " ) ").trim().split("\\s+");

        // Step 2: convert infix to postfix (shunting-yard)
        List<String> postfix = new ArrayList<>();
        Deque<String> ops = new ArrayDeque<>();
        for (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() && !ops.peek().equals("(") && precedence(ops.peek()) >= precedence(token)) {
                    postfix.add(ops.pop());
                }
                ops.push(token);
            } else {
                postfix.add(token);
            }
        }
        while (!ops.isEmpty()) {
            postfix.add(ops.pop());
        }

        // Step 3: evaluate the postfix expression on polynomials.
        // A polynomial maps a term key ("a*b", or "" for the constant) to its coefficient.
        Deque<Map<String, Integer>> stack = new ArrayDeque<>();
        for (String token : postfix) {
            if (isOperator(token)) {
                Map<String, Integer> right = stack.pop();
                Map<String, Integer> left = stack.pop();
                if (token.equals("*")) {
                    stack.push(multiply(left, right));
                } else {
                    stack.push(add(left, right, token.equals("+") ? 1 : -1));
                }
            } else {
                Map<String, Integer> poly = new HashMap<>();
                if (Character.isDigit(token.charAt(0))) {
                    poly.put("", Integer.parseInt(token));
                } else if (values.containsKey(token)) {
                    poly.put("", values.get(token));
                } else {
                    poly.put(token, 1);
                }
                stack.push(poly);
            }
        }
        Map<String, Integer> poly = stack.pop();

        // Step 4: drop zero terms, sort by degree (desc) then lexicographically
        List<String> keys = new ArrayList<>();
        for (String key : poly.keySet()) {
            if (poly.get(key) != 0) {
                keys.add(key);
            }
        }
        keys.sort((a, b) -> degree(a) != degree(b) ? degree(b) - degree(a) : a.compareTo(b));
        List<String> ans = new ArrayList<>();
        for (String key : keys) {
            ans.add(key.isEmpty() ? String.valueOf(poly.get(key)) : poly.get(key) + "*" + key);
        }
        return ans;
    }

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

    private int precedence(String op) {
        return op.equals("*") ? 2 : 1;
    }

    private int degree(String key) {
        return key.isEmpty() ? 0 : key.split("\\*").length;
    }

    private Map<String, Integer> add(Map<String, Integer> p, Map<String, Integer> q, int sign) {
        Map<String, Integer> res = new HashMap<>(p);
        for (Map.Entry<String, Integer> e : q.entrySet()) {
            res.merge(e.getKey(), sign * e.getValue(), Integer::sum);
        }
        return res;
    }

    private Map<String, Integer> multiply(Map<String, Integer> p, Map<String, Integer> q) {
        Map<String, Integer> res = new HashMap<>();
        for (Map.Entry<String, Integer> a : p.entrySet()) {
            for (Map.Entry<String, Integer> b : q.entrySet()) {
                List<String> vars = new ArrayList<>();
                if (!a.getKey().isEmpty()) vars.addAll(Arrays.asList(a.getKey().split("\\*")));
                if (!b.getKey().isEmpty()) vars.addAll(Arrays.asList(b.getKey().split("\\*")));
                Collections.sort(vars);
                res.merge(String.join("*", vars), a.getValue() * b.getValue(), Integer::sum);
            }
        }
        return res;
    }
}

JavaScript Solution

Copy
/**
 * @param {string} expression
 * @param {string[]} evalvars
 * @param {number[]} evalints
 * @return {string[]}
 */
var basicCalculatorIV = function (expression, evalvars, evalints) {
    const values = new Map();
    for (let i = 0; i < evalvars.length; i++) {
        values.set(evalvars[i], evalints[i]);
    }

    // A polynomial is a Map from a term key ("a*b", or "" for the constant) to its coefficient.
    const add = (p, q, sign) => {
        const res = new Map(p);
        for (const [key, coef] of q) {
            res.set(key, (res.get(key) || 0) + sign * coef);
        }
        return res;
    };
    const multiply = (p, q) => {
        const res = new Map();
        for (const [k1, c1] of p) {
            for (const [k2, c2] of q) {
                const vars = [];
                if (k1 !== '') vars.push(...k1.split('*'));
                if (k2 !== '') vars.push(...k2.split('*'));
                vars.sort();
                const key = vars.join('*');
                res.set(key, (res.get(key) || 0) + c1 * c2);
            }
        }
        return res;
    };

    // Step 1: tokenize (parentheses may touch their neighbors)
    const tokens = expression.replace(/\(/g, ' ( ').replace(/\)/g, ' ) ').trim().split(/\s+/);

    // Step 2: convert infix to postfix (shunting-yard)
    const precedence = { '+': 1, '-': 1, '*': 2 };
    const postfix = [];
    const ops = [];
    for (const token of tokens) {
        if (token === '(') {
            ops.push(token);
        } else if (token === ')') {
            while (ops[ops.length - 1] !== '(') {
                postfix.push(ops.pop());
            }
            ops.pop();
        } else if (token in precedence) {
            while (ops.length && ops[ops.length - 1] !== '(' && precedence[ops[ops.length - 1]] >= precedence[token]) {
                postfix.push(ops.pop());
            }
            ops.push(token);
        } else {
            postfix.push(token);
        }
    }
    while (ops.length) {
        postfix.push(ops.pop());
    }

    // Step 3: evaluate the postfix expression on polynomials
    const stack = [];
    for (const token of postfix) {
        if (token in precedence) {
            const right = stack.pop();
            const left = stack.pop();
            if (token === '*') {
                stack.push(multiply(left, right));
            } else {
                stack.push(add(left, right, token === '+' ? 1 : -1));
            }
        } else if (/^\d+$/.test(token)) {
            stack.push(new Map([['', parseInt(token)]]));
        } else if (values.has(token)) {
            stack.push(new Map([['', values.get(token)]]));
        } else {
            stack.push(new Map([[token, 1]]));
        }
    }
    const poly = stack.pop();

    // Step 4: drop zero terms, sort by degree (desc) then lexicographically
    const degree = (key) => (key === '' ? 0 : key.split('*').length);
    const keys = [...poly.keys()].filter((key) => poly.get(key) !== 0);
    keys.sort((a, b) => (degree(a) !== degree(b) ? degree(b) - degree(a) : a < b ? -1 : a > b ? 1 : 0));
    return keys.map((key) => (key === '' ? String(poly.get(key)) : poly.get(key) + '*' + key));
};

C# Solution

Copy
public class Solution {
    public IList<string> BasicCalculatorIV(string expression, string[] evalvars, int[] evalints) {
        var values = new Dictionary<string, int>();
        for (int i = 0; i < evalvars.Length; i++) {
            values[evalvars[i]] = evalints[i];
        }

        // Step 1: tokenize (parentheses may touch their neighbors)
        string[] tokens = expression.Replace("(", " ( ").Replace(")", " ) ")
            .Split(' ', StringSplitOptions.RemoveEmptyEntries);

        // Step 2: convert infix to postfix (shunting-yard)
        var postfix = new List<string>();
        var ops = new Stack<string>();
        foreach (string token in tokens) {
            if (token == "(") {
                ops.Push(token);
            } else if (token == ")") {
                while (ops.Peek() != "(") {
                    postfix.Add(ops.Pop());
                }
                ops.Pop();
            } else if (IsOperator(token)) {
                while (ops.Count > 0 && ops.Peek() != "(" && Precedence(ops.Peek()) >= Precedence(token)) {
                    postfix.Add(ops.Pop());
                }
                ops.Push(token);
            } else {
                postfix.Add(token);
            }
        }
        while (ops.Count > 0) {
            postfix.Add(ops.Pop());
        }

        // Step 3: evaluate the postfix expression on polynomials.
        // A polynomial maps a term key ("a*b", or "" for the constant) to its coefficient.
        var stack = new Stack<Dictionary<string, int>>();
        foreach (string token in postfix) {
            if (IsOperator(token)) {
                var right = stack.Pop();
                var left = stack.Pop();
                stack.Push(token == "*" ? Multiply(left, right) : Add(left, right, token == "+" ? 1 : -1));
            } else {
                var term = new Dictionary<string, int>();
                if (char.IsDigit(token[0])) {
                    term[""] = int.Parse(token);
                } else if (values.ContainsKey(token)) {
                    term[""] = values[token];
                } else {
                    term[token] = 1;
                }
                stack.Push(term);
            }
        }
        var poly = stack.Pop();

        // Step 4: drop zero terms, sort by degree (desc) then lexicographically
        var keys = new List<string>();
        foreach (var kv in poly) {
            if (kv.Value != 0) {
                keys.Add(kv.Key);
            }
        }
        keys.Sort((a, b) => Degree(a) != Degree(b) ? Degree(b) - Degree(a) : string.CompareOrdinal(a, b));
        var ans = new List<string>();
        foreach (string key in keys) {
            ans.Add(key == "" ? poly[key].ToString() : poly[key] + "*" + key);
        }
        return ans;
    }

    private bool IsOperator(string token) {
        return token == "+" || token == "-" || token == "*";
    }

    private int Precedence(string op) {
        return op == "*" ? 2 : 1;
    }

    private int Degree(string key) {
        return key == "" ? 0 : key.Split('*').Length;
    }

    private Dictionary<string, int> Add(Dictionary<string, int> p, Dictionary<string, int> q, int sign) {
        var res = new Dictionary<string, int>(p);
        foreach (var kv in q) {
            res.TryGetValue(kv.Key, out int cur);
            res[kv.Key] = cur + sign * kv.Value;
        }
        return res;
    }

    private Dictionary<string, int> Multiply(Dictionary<string, int> p, Dictionary<string, int> q) {
        var res = new Dictionary<string, int>();
        foreach (var a in p) {
            foreach (var b in q) {
                var vars = new List<string>();
                if (a.Key != "") vars.AddRange(a.Key.Split('*'));
                if (b.Key != "") vars.AddRange(b.Key.Split('*'));
                vars.Sort(string.CompareOrdinal);
                string key = string.Join("*", vars);
                res.TryGetValue(key, out int cur);
                res[key] = cur + a.Value * b.Value;
            }
        }
        return res;
    }
}

All four solutions follow the same four steps described in the approach. The expression is split into tokens, the shunting-yard algorithm converts the tokens to postfix order (multiplication has higher precedence than addition and subtraction, and parentheses override precedence), the postfix tokens are evaluated with a stack of polynomials, and the final polynomial is formatted.

Complexity

Let n be the length of the expression and T the number of terms in the largest intermediate polynomial. Tokenizing and the postfix conversion take O(n) time. Each multiplication can combine every pair of terms, so a single multiplication costs O(T^2 * L) time, where L is the length of a term key, and the final sort costs O(T log T * L). In the worst case T grows exponentially with the number of multiplied parenthesized sums, so the running time is bounded by the size of the expanded polynomial rather than by n alone. The space used is O(n + T * L) for the tokens, the stacks, and the polynomials.