Formatted question description: https://leetcode.ca/all/770.html

770. Basic Calculator IV (Hard)

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 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 degree equal to the number of free variables being multiplied, counting multiplicity. (For example, "a*a*b*c" has degree 4.) We write the largest degree terms of our answer first, breaking ties by lexicographic order ignoring the leading coefficient of the term.
  • 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 [].

Examples:

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

Input: expression = "e - 8 + temperature - pressure",
evalvars = ["e", "temperature"], evalints = [1, 12]
Output: ["-1*pressure","5"]

Input: expression = "(e + 8) * (e - 8)", evalvars = [], evalints = []
Output: ["1*e*e","-64"]

Input: expression = "7 - 7", evalvars = [], evalints = []
Output: []

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

Input: expression = "((a - b) * (b - c) + (c - a)) * ((a - b) + (b - c) * (c - a))",
evalvars = [], evalints = []
Output: ["-1*a*a*b*b","2*a*a*b*c","-1*a*a*c*c","1*a*b*b*b","-1*a*b*b*c","-1*a*b*c*c","1*a*c*c*c","-1*b*b*b*c","2*b*b*c*c","-1*b*c*c*c","2*a*a*b","-2*a*a*c","-2*a*b*b","2*a*c*c","1*b*b*b","-1*b*b*c","1*b*c*c","-1*c*c*c","-1*a*a","1*a*b","1*a*c","-1*b*c"]

Note:

  1. expression will have length in range [1, 250].
  2. evalvars, evalints will have equal lengths in range [0, 100].

Companies:
Intuit, Pinterest, Roblox

Related Topics:
Hash Table, String, Stack

Similar Questions:

Solution 1.

// OJ: https://leetcode.com/problems/basic-calculator-iv

class Solution {
private:
    vector<string> tokenize(string &expression) {
        vector<string> tokens;
        for (int i = 0; i < expression.size();) {
            string token;
            if (isalnum(expression[i])) {
                while (i < expression.size() && isalnum(expression[i])) {
                    token += expression[i++];
                }
            } else token += expression[i++];
            tokens.push_back(token);
            while (i < expression.size() && expression[i] == ' ') ++i;
        }
        return tokens;
    }
    vector<string> inject(vector<string> &tokens, unordered_map<string, string> &m) {
        for (auto &token : tokens) {
            if (m.find(token) != m.end()) token = m[token];
        }
        return tokens;
    }
    vector<string> toRPN(vector<string> &tokens) {
        stack<string> ops;
        vector<string> ans;
        for (auto &token : tokens) {
            switch(token.back()) {
                case '+':
                case '-':
                    while (ops.size() && ops.top() != "(") {
                        ans.push_back(ops.top());
                        ops.pop();
                    }
                    ops.push(token);
                    break;
                case '*':
                    if (ops.size() && ops.top() == "*") {
                        ans.push_back(ops.top());
                        ops.pop();
                    }
                    ops.push(token);
                    break;
                case '(':
                    ops.push(token);
                    break;
                case ')':
                    while (ops.size() && ops.top() != "(") {
                        ans.push_back(ops.top());
                        ops.pop();
                    }
                    if (ops.size()) ops.pop();
                    break;
                default:
                    ans.push_back(token);
                    break;
            }
        }
        while (ops.size()) {
            ans.push_back(ops.top());
            ops.pop();
        }
        return ans;
    }
    vector<string> splitSymbols(string exp) {
        istringstream s(exp);
        vector<string> ans;
        string symbol;
        while (getline(s, symbol, '*')) ans.push_back(symbol);
        return ans;
    }
    vector<string> evaluate(vector<string> &tokens) {
        stack<map<string, int>> s;
        for (auto &token : tokens) {
            switch(token.back()) {
                case '+':
                case '-': {
                    int sign = token[0] == '+' ? 1 : -1;
                    auto b = s.top(); s.pop();
                    auto a = s.top(); s.pop();
                    map<string, int> m;
                    for (auto &p : a) {
                        m[p.first] += p.second;
                    }
                    for (auto &p : b) {
                        m[p.first] += sign * p.second;
                    }
                    s.push(m);
                    break;
                }
                case '*': {
                    auto b = s.top(); s.pop();
                    auto a = s.top(); s.pop();
                    map<string, int> m;
                    for (auto &p : a) {
                        auto symbol1 = splitSymbols(p.first);
                        for (auto &q : b) {
                            istringstream sb(q.first);
                            auto symbol2 = splitSymbols(q.first);
                            string symbol;
                            if (symbol1.size() == 1 && symbol1[0] == "1") {
                                symbol = q.first;
                            } else if (symbol2.size() == 1 && symbol2[0] == "1") {
                                symbol = p.first;
                            } else {
                                for (int i = 0, j = 0; i < symbol1.size() || j < symbol2.size();) {
                                    if (symbol.size()) symbol += "*";
                                    if (i >= symbol1.size()) {
                                        symbol += symbol2[j++];
                                    } else if (j >= symbol2.size()) {
                                        symbol += symbol1[i++];
                                    } else if (symbol1[i] < symbol2[j]){
                                        symbol += symbol1[i++];
                                    } else {
                                        symbol += symbol2[j++];
                                    }
                                }
                            }
                            m[symbol] += p.second * q.second;
                        }
                    }
                    s.push(m);
                    break;
                }
                default: {
                    map<string, int> m;
                    if (isdigit(token.back())) {
                        m["1"] = stoi(token);
                    } else {
                        m[token] = 1;
                    }
                    s.push(m);
                    break;
                }
            }
        }
        vector<string> ans;
        for (auto &p : s.top()) {
            if (!p.second) continue;
            ans.push_back(to_string(p.second) + (p.first == "1" ? "" : "*" + p.first));
        }
        stable_sort(ans.begin(), ans.end(), [&](string a, string b) {
            return count(a.begin(), a.end(), '*') > count(b.begin(), b.end(), '*');
        });
        return ans;
    }
public:
    vector<string> basicCalculatorIV(string expression, vector<string>& evalvars, vector<int>& evalints) {
        unordered_map<string, string> m;
        for (int i = 0; i < evalvars.size(); ++i) {
            m[evalvars[i]] = to_string(evalints[i]);
        }
        auto tokens = tokenize(expression);
        tokens = inject(tokens, m);
        tokens = toRPN(tokens);
        tokens = evaluate(tokens);
        return tokens;
    }
};

Java

  • class Solution {
        public List<String> basicCalculatorIV(String expression, String[] evalvars, int[] evalints) {
            Polynomial polynomial = parse(expression);
            Map<String, Integer> evaluateMap = new HashMap<String, Integer>();
            int length = evalvars.length;
            for (int i = 0; i < length; i++)
                evaluateMap.put(evalvars[i], evalints[i]);
            Polynomial evaluation = polynomial.evaluate(evaluateMap);
            List<String> list = evaluation.toList();
            return list;
        }
    
        public Polynomial parse(String expression) {
            List<Polynomial> bucket = new ArrayList<Polynomial>();
            List<Character> operators = new ArrayList<Character>();
            int index = 0, length = expression.length();
            while (index < length) {
                if (expression.charAt(index) == '(') {
                    int balance = 0;
                    int curIndex = index;
                    while (curIndex < length) {
                        if (expression.charAt(curIndex) == '(')
                            balance++;
                        else if (expression.charAt(curIndex) == ')')
                            balance--;
                        if (balance == 0)
                            break;
                        curIndex++;
                    }
                    Polynomial curPolynomial = parse(expression.substring(index + 1, curIndex));
                    bucket.add(curPolynomial);
                    index = curIndex;
                } else if (Character.isLetterOrDigit(expression.charAt(index))) {
                    boolean flag = true;
                    int curIndex = index;
                    while (curIndex < length) {
                        if (expression.charAt(curIndex) == ' ') {
                            Polynomial curPolynomial = make(expression.substring(index, curIndex));
                            bucket.add(curPolynomial);
                            flag = false;
                            break;
                        }
                        curIndex++;
                    }
                    if (flag) {
                        Polynomial polynomial = make(expression.substring(index));
                        bucket.add(polynomial);
                    }
                    index = curIndex;
                } else if (expression.charAt(index) != ' ')
                    operators.add(expression.charAt(index));
                index++;
            }
            for (int i = operators.size() - 1; i >= 0; i--) {
                if (operators.get(i) == '*') {
                    Polynomial newPolynomial = combine(bucket.get(i), bucket.remove(i + 1), operators.remove(i));
                    bucket.set(i, newPolynomial);
                }
            }
            if (bucket.isEmpty())
                return new Polynomial();
            Polynomial polynomial = bucket.get(0);
            int size = operators.size();
            for (int i = 0; i < size; i++)
                polynomial = combine(polynomial, bucket.get(i + 1), operators.get(i));
            return polynomial;
        }
    
        public Polynomial make(String expression) {
            Polynomial polynomial = new Polynomial();
            List<String> list = new ArrayList<String>();
            if (Character.isDigit(expression.charAt(0)))
                polynomial.update(list, Integer.valueOf(expression));
            else {
                list.add(expression);
                polynomial.update(list, 1);
            }
            return polynomial;
        }
    
        public Polynomial combine(Polynomial polynomial1, Polynomial polynomial2, char operator) {
            if (operator == '+')
                return polynomial1.add(polynomial2);
            else if (operator == '-')
                return polynomial1.subtract(polynomial2);
            else if (operator == '*')
                return polynomial1.multiply(polynomial2);
            else
                return null;
        }
    }
    
    class Polynomial {
        Map<List<String>, Integer> countMap;
    
        public Polynomial() {
            countMap = new HashMap<List<String>, Integer>();
        }
    
        public void update(List<String> key, int count) {
            int newCount = countMap.getOrDefault(key, 0) + count;
            countMap.put(key, newCount);
        }
    
        public Polynomial add(Polynomial polynomial2) {
            Polynomial sum = new Polynomial();
            Set<List<String>> keySet1 = countMap.keySet();
            for (List<String> list : keySet1)
                sum.update(list, countMap.get(list));
            Set<List<String>> keySet2 = polynomial2.countMap.keySet();
            for (List<String> list : keySet2)
                sum.update(list, polynomial2.countMap.get(list));
            return sum;
        }
    
        public Polynomial subtract(Polynomial polynomial2) {
            Polynomial difference = new Polynomial();
            Set<List<String>> keySet1 = countMap.keySet();
            for (List<String> list : keySet1)
                difference.update(list, countMap.get(list));
            Set<List<String>> keySet2 = polynomial2.countMap.keySet();
            for (List<String> list : keySet2)
                difference.update(list, -polynomial2.countMap.get(list));
            return difference;
        }
    
        public Polynomial multiply(Polynomial polynomial2) {
            Polynomial product = new Polynomial();
            Set<List<String>> keySet1 = countMap.keySet();
            Set<List<String>> keySet2 = polynomial2.countMap.keySet();
            for (List<String> list1 : keySet1) {
                for (List<String> list2 : keySet2) {
                    List<String> newList = new ArrayList<String>();
                    for (String str : list1)
                        newList.add(str);
                    for (String str : list2)
                        newList.add(str);
                    Collections.sort(newList);
                    product.update(newList, countMap.get(list1) * polynomial2.countMap.get(list2));
                }
            }
            return product;
        }
    
        public Polynomial evaluate(Map<String, Integer> evaluateMap) {
            Polynomial polynomial = new Polynomial();
            Set<List<String>> keySet = countMap.keySet();
            for (List<String> list : keySet) {
                int count = countMap.get(list);
                List<String> freeList = new ArrayList<String>();
                for (String str : list) {
                    if (evaluateMap.containsKey(str))
                        count *= evaluateMap.get(str);
                    else
                        freeList.add(str);
                }
                polynomial.update(freeList, count);
            }
            return polynomial;
        }
    
        public int compareList(List<String> list1, List<String> list2) {
            int size1 = list1.size(), size2 = list2.size();
            if (size1 != size2)
                return size2 - size1;
            else {
                for (int i = 0; i < size1; i++) {
                    String str1 = list1.get(i), str2 = list2.get(i);
                    if (!str1.equals(str2))
                        return str1.compareTo(str2);
                }
                return 0;
            }
        }
    
        public List<String> toList() {
            List<String> list = new ArrayList<String>();
            List<List<String>> keyList = new ArrayList<List<String>>(countMap.keySet());
            Collections.sort(keyList, new Comparator<List<String>>() {
                public int compare(List<String> list1, List<String> list2) {
                    return compareList(list1, list2);
                }
            });
            for (List<String> key : keyList) {
                int count = countMap.get(key);
                if (count != 0) {
                    StringBuffer sb = new StringBuffer();
                    sb.append(count);
                    for (String str : key) {
                        sb.append('*');
                        sb.append(str);
                    }
                    list.add(sb.toString());
                }
            }
            return list;
        }
    }
    
  • // OJ: https://leetcode.com/problems/basic-calculator-iv
    class Solution {
    private:
        vector<string> tokenize(string &expression) {
            vector<string> tokens;
            for (int i = 0; i < expression.size();) {
                string token;
                if (isalnum(expression[i])) {
                    while (i < expression.size() && isalnum(expression[i])) {
                        token += expression[i++];
                    }
                } else token += expression[i++];
                tokens.push_back(token);
                while (i < expression.size() && expression[i] == ' ') ++i;
            }
            return tokens;
        }
        vector<string> inject(vector<string> &tokens, unordered_map<string, string> &m) {
            for (auto &token : tokens) {
                if (m.find(token) != m.end()) token = m[token];
            }
            return tokens;
        }
        vector<string> toRPN(vector<string> &tokens) {
            stack<string> ops;
            vector<string> ans;
            for (auto &token : tokens) {
                switch(token.back()) {
                    case '+':
                    case '-':
                        while (ops.size() && ops.top() != "(") {
                            ans.push_back(ops.top());
                            ops.pop();
                        }
                        ops.push(token);
                        break;
                    case '*':
                        if (ops.size() && ops.top() == "*") {
                            ans.push_back(ops.top());
                            ops.pop();
                        }
                        ops.push(token);
                        break;
                    case '(':
                        ops.push(token);
                        break;
                    case ')':
                        while (ops.size() && ops.top() != "(") {
                            ans.push_back(ops.top());
                            ops.pop();
                        }
                        if (ops.size()) ops.pop();
                        break;
                    default:
                        ans.push_back(token);
                        break;
                }
            }
            while (ops.size()) {
                ans.push_back(ops.top());
                ops.pop();
            }
            return ans;
        }
        vector<string> splitSymbols(string exp) {
            istringstream s(exp);
            vector<string> ans;
            string symbol;
            while (getline(s, symbol, '*')) ans.push_back(symbol);
            return ans;
        }
        vector<string> evaluate(vector<string> &tokens) {
            stack<map<string, int>> s;
            for (auto &token : tokens) {
                switch(token.back()) {
                    case '+':
                    case '-': {
                        int sign = token[0] == '+' ? 1 : -1;
                        auto b = s.top(); s.pop();
                        auto a = s.top(); s.pop();
                        map<string, int> m;
                        for (auto &p : a) {
                            m[p.first] += p.second;
                        }
                        for (auto &p : b) {
                            m[p.first] += sign * p.second;
                        }
                        s.push(m);
                        break;
                    }
                    case '*': {
                        auto b = s.top(); s.pop();
                        auto a = s.top(); s.pop();
                        map<string, int> m;
                        for (auto &p : a) {
                            auto symbol1 = splitSymbols(p.first);
                            for (auto &q : b) {
                                istringstream sb(q.first);
                                auto symbol2 = splitSymbols(q.first);
                                string symbol;
                                if (symbol1.size() == 1 && symbol1[0] == "1") {
                                    symbol = q.first;
                                } else if (symbol2.size() == 1 && symbol2[0] == "1") {
                                    symbol = p.first;
                                } else {
                                    for (int i = 0, j = 0; i < symbol1.size() || j < symbol2.size();) {
                                        if (symbol.size()) symbol += "*";
                                        if (i >= symbol1.size()) {
                                            symbol += symbol2[j++];
                                        } else if (j >= symbol2.size()) {
                                            symbol += symbol1[i++];
                                        } else if (symbol1[i] < symbol2[j]){
                                            symbol += symbol1[i++];
                                        } else {
                                            symbol += symbol2[j++];
                                        }
                                    }
                                }
                                m[symbol] += p.second * q.second;
                            }
                        }
                        s.push(m);
                        break;
                    }
                    default: {
                        map<string, int> m;
                        if (isdigit(token.back())) {
                            m["1"] = stoi(token);
                        } else {
                            m[token] = 1;
                        }
                        s.push(m);
                        break;
                    }
                }
            }
            vector<string> ans;
            for (auto &p : s.top()) {
                if (!p.second) continue;
                ans.push_back(to_string(p.second) + (p.first == "1" ? "" : "*" + p.first));
            }
            stable_sort(ans.begin(), ans.end(), [&](string a, string b) {
                return count(a.begin(), a.end(), '*') > count(b.begin(), b.end(), '*');
            });
            return ans;
        }
    public:
        vector<string> basicCalculatorIV(string expression, vector<string>& evalvars, vector<int>& evalints) {
            unordered_map<string, string> m;
            for (int i = 0; i < evalvars.size(); ++i) {
                m[evalvars[i]] = to_string(evalints[i]);
            }
            auto tokens = tokenize(expression);
            tokens = inject(tokens, m);
            tokens = toRPN(tokens);
            tokens = evaluate(tokens);
            return tokens;
        }
    };
    
  • print("Todo!")
    

All Problems

All Solutions