770. 基础计算器 IV

class Solution {
private:
    struct Poly {
        map<vector<string>, int> terms;
        
        Poly() {}
        Poly(int val) { if (val) terms[{}] = val; }
        Poly(string var) { terms[{var}] = 1; }
        
        Poly operator+(const Poly& other) const {
            Poly result = *this;
            for (auto& p : other.terms) {
                result.terms[p.first] += p.second;
                if (result.terms[p.first] == 0) {
                    result.terms.erase(p.first);
                }
            }
            return result;
        }
        
        Poly operator-(const Poly& other) const {
            Poly result = *this;
            for (auto& p : other.terms) {
                result.terms[p.first] -= p.second;
                if (result.terms[p.first] == 0) {
                    result.terms.erase(p.first);
                }
            }
            return result;
        }
        
        Poly operator*(const Poly& other) const {
            Poly result;
            for (auto& p1 : terms) {
                for (auto& p2 : other.terms) {
                    vector<string> vars = p1.first;
                    vars.insert(vars.end(), p2.first.begin(), p2.first.end());
                    sort(vars.begin(), vars.end());
                    result.terms[vars] += p1.second * p2.second;
                }
            }
            for (auto it = result.terms.begin(); it != result.terms.end();) {
                if (it->second == 0) it = result.terms.erase(it);
                else ++it;
            }
            return result;
        }
        
        void evaluate(unordered_map<string, int>& evalMap) {
            map<vector<string>, int> newTerms;
            for (auto& p : terms) {
                vector<string> newVars;
                int coeff = p.second;
                for (string& var : p.first) {
                    if (evalMap.count(var)) {
                        coeff *= evalMap[var];
                    } else {
                        newVars.push_back(var);
                    }
                }
                if (coeff) newTerms[newVars] += coeff;
            }
            terms = newTerms;
        }
    };
    
    vector<string> tokenize(string& expression) {
        vector<string> tokens;
        istringstream iss(expression);
        string token;
        while (iss >> token) tokens.push_back(token);
        return tokens;
    }
    
    Poly parse(vector<string>& tokens, int& pos) {
        return parseExpression(tokens, pos);
    }
    
    Poly parseExpression(vector<string>& tokens, int& pos) {
        Poly result = parseTerm(tokens, pos);
        while (pos < tokens.size() && (tokens[pos] == "+" || tokens[pos] == "-")) {
            string op = tokens[pos++];
            Poly term = parseTerm(tokens, pos);
            if (op == "+") result = result + term;
            else result = result - term;
        }
        return result;
    }
    
    Poly parseTerm(vector<string>& tokens, int& pos) {
        Poly result = parseFactor(tokens, pos);
        while (pos < tokens.size() && tokens[pos] == "*") {
            pos++;
            result = result * parseFactor(tokens, pos);
        }
        return result;
    }
    
    Poly parseFactor(vector<string>& tokens, int& pos) {
        if (tokens[pos] == "(") {
            pos++;
            Poly result = parseExpression(tokens, pos);
            pos++; // skip ")"
            return result;
        } else if (isdigit(tokens[pos][0])) {
            return Poly(stoi(tokens[pos++]));
        } else {
            return Poly(tokens[pos++]);
        }
    }
    
public:
    vector<string> basicCalculatorIV(string expression, vector<string>& evalvars, vector<int>& evalints) {
        unordered_map<string, int> evalMap;
        for (int i = 0; i < evalvars.size(); i++) {
            evalMap[evalvars[i]] = evalints[i];
        }
        
        vector<string> tokens = tokenize(expression);
        int pos = 0;
        Poly poly = parse(tokens, pos);
        poly.evaluate(evalMap);
        
        vector<pair<vector<string>, int>> termsList;
        for (auto& p : poly.terms) {
            termsList.push_back(p);
        }
        
        sort(termsList.begin(), termsList.end(), [](const auto& a, const auto& b) {
            if (a.first.size() != b.first.size()) 
                return a.first.size() > b.first.size();
            return a.first < b.first;
        });
        
        vector<string> result;
        for (auto& term : termsList) {
            string s = to_string(term.second);
            if (!term.first.empty()) {
                s += "*";
                for (int i = 0; i < term.first.size(); i++) {
                    if (i > 0) s += "*";
                    s += term.first[i];
                }
            }
            result.push_back(s);
        }
        
        return result;
    }
};

class Solution:
    def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:
        class Poly:
            def __init__(self, terms=None):
                self.terms = terms if terms else {}
            
            @classmethod
            def from_int(cls, val):
                poly = cls()
                if val:
                    poly.terms[tuple()] = val
                return poly
            
            @classmethod
            def from_var(cls, var):
                poly = cls()
                poly.terms[(var,)] = 1
                return poly
            
            def __add__(self, other):
                result = Poly(dict(self.terms))
                for key, val in other.terms.items():
                    result.terms[key] = result.terms.get(key, 0) + val
                    if result.terms[key] == 0:
                        del result.terms[key]
                return result
            
            def __sub__(self, other):
                result = Poly(dict(self.terms))
                for key, val in other.terms.items():
                    result.terms[key] = result.terms.get(key, 0) - val
                    if result.terms[key] == 0:
                        del result.terms[key]
                return result
            
            def __mul__(self, other):
                result = Poly()
                for key1, val1 in self.terms.items():
                    for key2, val2 in other.terms.items():
                        new_key = tuple(sorted(key1 + key2))
                        result.terms[new_key] = result.terms.get(new_key, 0) + val1 * val2
                for key in list(result.terms.keys()):
                    if result.terms[key] == 0:
                        del result.terms[key]
                return result
            
            def evaluate(self, eval_map):
                new_terms = {}
                for key, coeff in self.terms.items():
                    new_key = []
                    for var in key:
                        if var in eval_map:
                            coeff *= eval_map[var]
                        else:
                            new_key.append(var)
                    if coeff:
                        new_key = tuple(sorted(new_key))
                        new_terms[new_key] = new_terms.get(new_key, 0) + coeff
                self.terms = new_terms
        
        def parse_expression(tokens, pos):
            result = parse_term(tokens, pos)
            while pos[0] < len(tokens) and tokens[pos[0]] in ['+', '-']:
                op = tokens[pos[0]]
                pos[0] += 1
                term = parse_term(tokens, pos)
                if op == '+':
                    result = result + term
                else:
                    result = result - term
            return result
        
        def parse_term(tokens, pos):
            result = parse_factor(tokens, pos)
            while pos[0] < len(tokens) and tokens[pos[0]] == '*':
                pos[0] += 1
                result = result * parse_factor(tokens, pos)
            return result
        
        def parse_factor(tokens, pos):
            if tokens[pos[0]] == '(':
                pos[0] += 1
                result = parse_expression(tokens, pos)
                pos[0] += 1  # skip ')'
                return result
            elif tokens[pos[0]].isdigit():
                val = int(tokens[pos[0]])
                pos[0] += 1
                return Poly.from_int(val)
            else:
                var = tokens[pos[0]]
                pos[0] += 1
                return Poly.from_var(var)
        
        eval_map = dict(zip(evalvars, evalints))
        tokens = expression.split()
        pos = [0]
        poly = parse_expression(tokens, pos)
        poly.evaluate(eval_map)
        
        # Sort terms by degree (descending) then lexicographically
        terms_list = list(poly.terms.items())
        terms_list.sort(key=lambda x: (-len(x[0]), x[0]))
        
        result = []
        for key, coeff in terms_list:
            s = str(coeff)
            if key:
                s += '*' + '*'.join(key)
            result.append(s)
        
        return result

public class Solution {
    public class Poly {
        public Dictionary<List<string>, int> terms;
        
        public Poly() {
            terms = new Dictionary<List<string>, int>(new ListComparer());
        }
        
        public Poly(int val) : this() {
            if (val != 0) terms[new List<string>()] = val;
        }
        
        public Poly(string var) : this() {
            terms[new List<string> { var }] = 1;
        }
        
        public Poly Add(Poly other) {
            var result = new Poly();
            foreach (var kvp in terms) {
                result.terms[new List<string>(kvp.Key)] = kvp.Value;
            }
            foreach (var kvp in other.terms) {
                var key = new List<string>(kvp.Key);
                if (result.terms.ContainsKey(key)) {
                    result.terms[key] += kvp.Value;
                    if (result.terms[key] == 0) result.terms.Remove(key);
                } else {
                    result.terms[key] = kvp.Value;
                }
            }
            return result;
        }
        
        public Poly Subtract(Poly other) {
            var result = new Poly();
            foreach (var kvp in terms) {
                result.terms[new List<string>(kvp.Key)] = kvp.Value;
            }
            foreach (var kvp in other.terms) {
                var key = new List<string>(kvp.Key);
                if (result.terms.ContainsKey(key)) {
                    result.terms[key] -= kvp.Value;
                    if (result.terms[key] == 0) result.terms.Remove(key);
                } else {
                    result.terms[key] = -kvp.Value;
                }
            }
            return result;
        }
        
        public Poly Multiply(Poly other) {
            var result = new Poly();
            foreach (var kvp1 in terms) {
                foreach (var kvp2 in other.terms) {
                    var newKey = new List<string>(kvp1.Key);
                    newKey.AddRange(kvp2.Key);
                    newKey.Sort();
                    
                    if (result.terms.ContainsKey(newKey)) {
                        result.terms[newKey] += kvp1.Value * kvp2.Value;
                    } else {
                        result.terms[newKey] = kvp1.Value * kvp2.Value;
                    }
                }
            }
            var keysToRemove = new List<List<string>>();
            foreach (var kvp in result.terms) {
                if (kvp.Value == 0) keysToRemove.Add(kvp.Key);
            }
            foreach (var key in keysToRemove) {
                result.terms.Remove(key);
            }
            return result;
        }
        
        public void Evaluate(Dictionary<string, int> evalMap) {
            var newTerms = new Dictionary<List<string>, int>(new ListComparer());
            foreach (var kvp in terms) {
                var newKey = new List<string>();
                int coeff = kvp.Value;
                foreach (var var in kvp.Key) {
                    if (evalMap.ContainsKey(var)) {
                        coeff *= evalMap[var];
                    } else {
                        newKey.Add(var);
                    }
                }
                if (coeff != 0) {
                    newKey.Sort();
                    if (newTerms.ContainsKey(newKey)) {
                        newTerms[newKey] += coeff;
                    } else {
                        newTerms[newKey] = coeff;
                    }
                }
            }
            terms = newTerms;
        }
    }
    
    public class ListComparer : IEqualityComparer<List<string>> {
        public bool Equals(List<string> x, List<string> y) {
            if (x.Count != y.Count) return false;
            for (int i = 0; i < x.Count; i++) {
                if (x[i] != y[i]) return false;
            }
            return true;
        }
        
        public int GetHashCode(List<string> obj) {
            int hash = 17;
            foreach (var item in obj) {
                hash = hash * 31 + item.GetHashCode();
            }
            return hash;
        }
    }
    
    private int pos;
    
    public IList<string> BasicCalculatorIV(string expression, string[] evalvars, int[] evalints) {
        var evalMap = new Dictionary<string, int>();
        for (int i = 0; i < evalvars.Length; i++) {
            evalMap[evalvars[i]] = evalints[i];
        }
        
        var tokens = expression.Split(' ');
        pos = 0;
        var poly = ParseExpression(tokens);
        poly.Evaluate(evalMap);
        
        var termsList = poly.terms.ToList();
        termsList.Sort((a, b) => {
            if (a.Key.Count != b.Key.Count) return b.Key.Count.CompareTo(a.Key.Count);
            return string.Join("", a.Key).CompareTo(string.Join("", b.Key));
        });
        
        var result = new List<string>();
        foreach (var term in termsList) {
            var s = term.Value.ToString();
            if (term.Key.Count > 0) {
                s += "*" + string.Join("*", term.Key);
            }
            result.Add(s);
        }
        
        return result;
    }
    
    private Poly ParseExpression(string[] tokens) {
        var result = ParseTerm(tokens);
        while (pos < tokens.Length && (tokens[pos] == "+" || tokens[pos] == "-")) {
            var op = tokens[pos++];
            var term = ParseTerm(tokens);
            if (op == "+") result = result.Add(term);
            else result = result.Subtract(term);
        }
        return result;
    }
    
    private Poly ParseTerm(string[] tokens) {
        var result = ParseFactor(tokens);
        while (pos < tokens.Length && tokens[pos] == "*") {
            pos++;
            result = result.Multiply(ParseFactor(tokens));
        }
        return result;
    }
    
    private Poly ParseFactor(string[] tokens) {
        if (tokens[pos] == "(") {
            pos++;
            var result = ParseExpression(tokens);
            pos++; // skip ")"
            return result;
        } else if (char.IsDigit(tokens[pos][0])) {
            return new Poly(int.Parse(tokens[pos++]));
        } else {
            return new Poly(tokens[pos++]);
        }
    }
}

var basicCalculatorIV = function(expression, evalvars, evalints) {
    const evalMap = {};
    for (let i = 0; i < evalvars.length; i++) {
        evalMap[evalvars[i]] = evalints[i];
    }
    
    class Term {
        constructor(coeff = 0, vars = []) {
            this.coeff = coeff;
            this.vars = vars.slice().sort();
        }
        
        multiply(other) {
            return new Term(this.coeff * other.coeff, this.vars.concat(other.vars));
        }
        
        getKey() {
            return this.vars.join('*');
        }
        
        getDegree() {
            return this.vars.length;
        }
    }
    
    class Polynomial {
        constructor() {
            this.terms = new Map();
        }
        
        addTerm(term) {
            const key = term.getKey();
            if (this.terms.has(key)) {
                this.terms.get(key).coeff += term.coeff;
            } else {
                this.terms.set(key, new Term(term.coeff, term.vars));
            }
        }
        
        add(other) {
            const result = new Polynomial();
            for (let term of this.terms.values()) {
                result.addTerm(term);
            }
            for (let term of other.terms.values()) {
                result.addTerm(term);
            }
            return result;
        }
        
        multiply(other) {
            const result = new Polynomial();
            for (let term1 of this.terms.values()) {
                for (let term2 of other.terms.values()) {
                    result.addTerm(term1.multiply(term2));
                }
            }
            return result;
        }
        
        toResult() {
            const terms = Array.from(this.terms.values()).filter(term => term.coeff !== 0);
            terms.sort((a, b) => {
                if (a.getDegree() !== b.getDegree()) {
                    return b.getDegree() - a.getDegree();
                }
                return a.getKey().localeCompare(b.getKey());
            });
            
            return terms.map(term => {
                if (term.vars.length === 0) {
                    return term.coeff.toString();
                } else {
                    return term.coeff + '*' + term.vars.join('*');
                }
            });
        }
    }
    
    function parseTerm(token) {
        if (/^\d+$/.test(token)) {
            const poly = new Polynomial();
            poly.addTerm(new Term(parseInt(token), []));
            return poly;
        } else if (evalMap.hasOwnProperty(token)) {
            const poly = new Polynomial();
            poly.addTerm(new Term(evalMap[token], []));
            return poly;
        } else {
            const poly = new Polynomial();
            poly.addTerm(new Term(1, [token]));
            return poly;
        }
    }
    
    function parseExpression(tokens, index) {
        let result = parseFactor(tokens, index);
        
        while (index.value < tokens.length && (tokens[index.value] === '+' || tokens[index.value] === '-')) {
            const op = tokens[index.value];
            index.value++;
            const right = parseFactor(tokens, index);
            if (op === '+') {
                result = result.add(right);
            } else {
                const negRight = new Polynomial();
                for (let term of right.terms.values()) {
                    negRight.addTerm(new Term(-term.coeff, term.vars));
                }
                result = result.add(negRight);
            }
        }
        
        return result;
    }
    
    function parseFactor(tokens, index) {
        let result = parseAtom(tokens, index);
        
        while (index.value < tokens.length && tokens[index.value] === '*') {
            index.value++;
            const right = parseAtom(tokens, index);
            result = result.multiply(right);
        }
        
        return result;
    }
    
    function parseAtom(tokens, index) {
        if (tokens[index.value] === '(') {
            index.value++;
            const result = parseExpression(tokens, index);
            index.value++;
            return result;
        } else {
            const result = parseTerm(tokens[index.value]);
            index.value++;
            return result;
        }
    }
    
    const tokens = expression.split(' ');
    const index = { value: 0 };
    const result = parseExpression(tokens, index);
    
    return result.toResult();
};