770. Basic Calculator IV¶

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 class Poly { friend Poly operator+(const Poly& lhs, const Poly& rhs) { Poly res(lhs); for (const auto& [term, coef] : rhs.terms) res.terms[term] += coef; return res; } friend Poly operator-(const Poly& lhs, const Poly& rhs) { Poly res(lhs); for (const auto& [term, coef] : rhs.terms) res.terms[term] -= coef; return res; } friend Poly operator*(const Poly& lhs, const Poly& rhs) { Poly res; for (const auto& [a, aCoef] : lhs.terms) for (const auto& [b, bCoef] : rhs.terms) res.terms[merge(a, b)] += aCoef * bCoef; return res; } // Friend ostream& operator<<(ostream& os, const Poly& poly) { // os << "{"; // for (const auto& [term, coef] : poly.terms) // os << term << ": " << coef << ", "; // os << "}"; // return os; // } public: vector toList() { vector res; vector keys; for (const auto& [term, _] : terms) keys.push_back(term); ranges::sort(keys, [&](const string& a, const string& b) { // the minimum degree is the last if (a == "1") return false; if (b == "1") return true; const vector as = split(a, '*'); const vector bs = split(b, '*'); // the maximum degree is the first // Break ties by their lexicographic orders. return as.size() == bs.size() ? a < b : as.size() > bs.size(); }); auto concat = [&](const string& term) -> string { if (term == "1") return to_string(terms[term]); return to_string(terms[term]) + '*' + term; }; for (const string& key : keys) if (terms[key]) res.push_back(concat(key)); return res; } Poly() = default; Poly(const string& term, int coef) { terms[term] = coef; } private: unordered_map terms; // e.g. merge("a*b", "a*c") -> "a*a*b*c" static string merge(const string& a, const string& b) { if (a == "1") return b; if (b == "1") return a; string res; vector A = split(a, '*'); vector B = split(b, '*'); int i = 0; // A's index int j = 0; // B's index while (i < A.size() && j < B.size()) if (A[i] < B[j]) res += '*' + A[i++]; else res += '*' + B[j++]; while (i < A.size()) res += '*' + A[i++]; while (j < B.size()) res += '*' + B[j++]; return res.substr(1); } static vector split(const string& token, char c) { vector vars; istringstream iss(token); for (string var; getline(iss, var, c);) vars.push_back(var); return vars; } }; class Solution { public: vector basicCalculatorIV(string expression, vector& evalvars, vector& evalints) { vector tokens = getTokens(expression); unordered_map evalMap; for (int i = 0; i < evalvars.size(); ++i) evalMap[evalvars[i]] = evalints[i]; for (string& token : tokens) if (const auto it = evalMap.find(token); it != evalMap.cend()) token = to_string(it->second); const vector& postfix = infixToPostfix(tokens); return evaluate(postfix).toList(); } private: vector getTokens(const string& s) { vector tokens; int i = 0; for (int j = 0; j < s.length(); ++j) if (s[j] == ' ') { if (i < j) tokens.push_back(s.substr(i, j - i)); i = j + 1; } else if (string("()+-*").find(s[j]) != string::npos) { if (i < j) tokens.push_back(s.substr(i, j - i)); tokens.push_back(s.substr(j, 1)); i = j + 1; } if (i < s.length()) tokens.push_back(s.substr(i)); return tokens; } bool isOperator(const string& token) { return token == "+" || token == "-" || token == "*"; } vector infixToPostfix(const vector& tokens) { vector postfix; stack ops; auto precedes = [](const string& prevOp, const string& currOp) -> bool { if (prevOp == "(") return false; return prevOp == "*" || currOp == "+" || currOp == "-"; }; for (const string& token : tokens) if (token == "(") { ops.push(token); } else if (token == ")") { while (ops.top() != "(") postfix.push_back(ops.top()), ops.pop(); ops.pop(); } else if (isOperator(token)) { while (!ops.empty() && precedes(ops.top(), token)) postfix.push_back(ops.top()), ops.pop(); ops.push(token); } else { // isOperand(token) postfix.push_back(token); } while (!ops.empty()) postfix.push_back(ops.top()), ops.pop(); return postfix; } Poly evaluate(const vector& postfix) { vector polys; for (const string& token : postfix) if (isOperator(token)) { const Poly b = polys.back(); polys.pop_back(); const Poly a = polys.back(); polys.pop_back(); if (token == "+") polys.push_back(a + b); else if (token == "-") polys.push_back(a - b); else // token == "*" polys.push_back(a * b); } else if (token[0] == '-' || ranges::all_of(token, [](char c) { return isdigit(c); })) { polys.push_back(Poly("1", stoi(token))); } else { polys.push_back(Poly(token, 1)); } return polys[0]; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 class Poly { public Poly add(Poly o) { for (final String term : o.terms.keySet()) terms.merge(term, o.terms.get(term), Integer::sum); return this; } public Poly minus(Poly o) { for (final String term : o.terms.keySet()) terms.merge(term, -o.terms.get(term), Integer::sum); return this; } public Poly mult(Poly o) { Poly res = new Poly(); for (final String a : terms.keySet()) for (final String b : o.terms.keySet()) res.terms.merge(merge(a, b), terms.get(a) * o.terms.get(b), Integer::sum); return res; } // @Override // Public String toString() { // StringBuilder sb = new StringBuilder(); // sb.append("{"); // for (final String term : terms.keySet()) // sb.append(term).append(": ").append(terms.get(term)).append(", "); // sb.append("}"); // return sb.toString(); // } public List toList() { List res = new ArrayList<>(); List keys = new ArrayList<>(terms.keySet()); Collections.sort(keys, new Comparator() { @Override public int compare(final String a, final String b) { // the minimum degree is the last if (a.equals("1")) return 1; if (b.equals("1")) return -1; String[] as = a.split("\\*"); String[] bs = b.split("\\*"); // the maximum degree is the first // Break ties by their lexicographic orders. return as.length == bs.length ? a.compareTo(b) : bs.length - as.length; } }); for (final String key : keys) if (terms.get(key) != 0) res.add(concat(key)); return res; } public Poly() {} public Poly(final String term, int coef) { terms.put(term, coef); } private Map terms = new HashMap<>(); // e.g. merge("a*b", "a*c") -> "a*a*b*c" private static String merge(final String a, final String b) { if (a.equals("1")) return b; if (b.equals("1")) return a; StringBuilder sb = new StringBuilder(); String[] A = a.split("\\*"); String[] B = b.split("\\*"); int i = 0; // A's index int j = 0; // B's index while (i < A.length && j < B.length) if (A[i].compareTo(B[j]) < 0) sb.append("*").append(A[i++]); else sb.append("*").append(B[j++]); while (i < A.length) sb.append("*").append(A[i++]); while (j < B.length) sb.append("*").append(B[j++]); return sb.substring(1).toString(); } private String concat(final String term) { if (term.equals("1")) return String.valueOf(terms.get(term)); return new StringBuilder().append(terms.get(term)).append('*').append(term).toString(); } } class Solution { public List basicCalculatorIV(String expression, String[] evalvars, int[] evalints) { List tokens = getTokens(expression); Map evalMap = new HashMap<>(); for (int i = 0; i < evalvars.length; ++i) evalMap.put(evalvars[i], evalints[i]); for (int i = 0; i < tokens.size(); ++i) if (evalMap.containsKey(tokens.get(i))) tokens.set(i, String.valueOf(evalMap.get(tokens.get(i)))); List postfix = infixToPostfix(tokens); return evaluate(postfix).toList(); } private List getTokens(final String s) { List tokens = new ArrayList<>(); int i = 0; for (int j = 0; j < s.length(); ++j) if (s.charAt(j) == ' ') { if (i < j) tokens.add(s.substring(i, j)); i = j + 1; } else if ("()+-*".contains(s.substring(j, j + 1))) { if (i < j) tokens.add(s.substring(i, j)); tokens.add(s.substring(j, j + 1)); i = j + 1; } if (i < s.length()) tokens.add(s.substring(i)); return tokens; } private boolean isOperator(final String token) { return token.equals("+") || token.equals("-") || token.equals("*"); } private boolean precedes(final String prevOp, final String currOp) { if (prevOp.equals("(")) return false; return prevOp.equals("*") || currOp.equals("+") || currOp.equals("-"); } private List infixToPostfix(List tokens) { List postfix = new ArrayList<>(); Deque ops = new ArrayDeque<>(); for (final 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() && precedes(ops.peek(), token)) postfix.add(ops.pop()); ops.push(token); } else { // isOperand(token) postfix.add(token); } while (!ops.isEmpty()) postfix.add(ops.pop()); return postfix; } private Poly evaluate(List postfix) { LinkedList polys = new LinkedList<>(); for (final String token : postfix) if (isOperator(token)) { final Poly b = polys.removeLast(); final Poly a = polys.removeLast(); if (token.equals("+")) polys.add(a.add(b)); else if (token.equals("-")) polys.add(a.minus(b)); else // token == "*" polys.add(a.mult(b)); } else if (token.charAt(0) == '-' || token.chars().allMatch(c -> Character.isDigit(c))) { polys.add(new Poly("1", Integer.parseInt(token))); } else { polys.add(new Poly(token, 1)); } return polys.getFirst(); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 class Poly: def __init__(self, term: str = None, coef: int = None): if term and coef: self.terms = collections.Counter({term: coef}) else: self.terms = collections.Counter() def __add__(self, other): for term, coef in other.terms.items(): self.terms[term] += coef return self def __sub__(self, other): for term, coef in other.terms.items(): self.terms[term] -= coef return self def __mul__(self, other): res = Poly() for a, aCoef in self.terms.items(): for b, bCoef in other.terms.items(): res.terms[self._merge(a, b)] += aCoef * bCoef return res # Def __str__(self): # res = [] # for term, coef in self.terms.items(): # res.append(term + ': ' + str(coef)) # return '{' + ', '.join(res) + '}' def toList(self) -> list[str]: for term in list(self.terms.keys()): if not self.terms[term]: del self.terms[term] def cmp(term: str) -> tuple: # the minimum degree is the last if term == '1': return (0,) var = term.split('*') # the maximum degree is the first # Break ties by their lexicographic orders. return (-len(var), term) def concat(term: str) -> str: if term == '1': return str(self.terms[term]) return str(self.terms[term]) + '*' + term terms = list(self.terms.keys()) terms.sort(key=cmp) return [concat(term) for term in terms] def _merge(self, a: str, b: str) -> str: if a == '1': return b if b == '1': return a res = [] A = a.split('*') B = b.split('*') i = 0 # A's index j = 0 # B's index while i < len(A) and j < len(B): if A[i] < B[j]: res.append(A[i]) i += 1 else: res.append(B[j]) j += 1 return '*'.join(res + A[i:] + B[j:]) class Solution: def basicCalculatorIV( self, expression: str, evalvars: list[str], evalints: list[int], ) -> list[str]: tokens = list(self._getTokens(expression)) evalMap = {a: b for a, b in zip(evalvars, evalints)} for i, token in enumerate(tokens): if token in evalMap: tokens[i] = str(evalMap[token]) postfix = self._infixToPostfix(tokens) return self._evaluate(postfix).toList() def _getTokens(self, s: str) -> Iterator[str]: i = 0 for j, c in enumerate(s): if c == ' ': if i < j: yield s[i:j] i = j + 1 elif c in '()+-*': if i < j: yield s[i:j] yield c i = j + 1 if i < len(s): yield s[i:] def _infixToPostfix(self, tokens: list[str]) -> list[str]: postfix = [] ops = [] def precedes(prevOp: str, currOp: str) -> bool: if prevOp == '(': return False return prevOp == '*' or currOp in '+-' for token in tokens: if token == '(': ops.append(token) elif token == ')': while ops[-1] != '(': postfix.append(ops.pop()) ops.pop() elif token in '+-*': # isOperator(token) while ops and precedes(ops[-1], token): postfix.append(ops.pop()) ops.append(token) else: # isOperand(token) postfix.append(token) return postfix + ops[::-1] def _evaluate(self, postfix: list[str]) -> Poly: polys: list[Poly] = [] for token in postfix: if token in '+-*': b = polys.pop() a = polys.pop() if token == '+': polys.append(a + b) elif token == '-': polys.append(a - b) else: # token == '*' polys.append(a * b) elif token.lstrip('-').isnumeric(): polys.append(Poly("1", int(token))) else: polys.append(Poly(token, 1)) return polys[0]