Welcome to Subscribe On Youtube
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:
expressionwill have length in range[1, 250].evalvars, evalintswill have equal lengths in range[0, 100].
Companies:
Intuit, Pinterest, Roblox
Related Topics:
Hash Table, String, Stack
Similar Questions:
Solution 1.
-
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; } };