LeetCode Solutions

			

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<string> toList() {
    vector<string> res;
    vector<string> keys;
    for (const auto& [term, _] : terms)
      keys.push_back(term);
    sort(begin(keys), end(keys), [&](const auto& a, const auto& b) {
      // Smallest degree is the last
      if (a == "1")
        return false;
      if (b == "1")
        return true;
      const vector<string> as = split(a, '*');
      const vector<string> bs = split(b, '*');
      // Largest degree is the first
      // Breaking ties by lexicographic order
      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<string, int> 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<string> A = split(a, '*');
    vector<string> 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<string> split(const string& token, char c) {
    vector<string> vars;
    istringstream iss(token);
    for (string var; getline(iss, var, c);)
      vars.push_back(var);
    return vars;
  }
};

class Solution {
 public:
  vector<string> basicCalculatorIV(string expression, vector<string>& evalvars,
                                   vector<int>& evalints) {
    vector<string> tokens = getTokens(expression);
    unordered_map<string, int> evalMap;

    for (int i = 0; i < evalvars.size(); ++i)
      evalMap[evalvars[i]] = evalints[i];

    for (string& token : tokens)
      if (evalMap.count(token))
        token = to_string(evalMap[token]);

    const vector<string>& postfix = infixToPostfix(tokens);
    return evaluate(postfix).toList();
  }

 private:
  vector<string> getTokens(const string& s) {
    vector<string> 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<string> infixToPostfix(const vector<string>& tokens) {
    vector<string> postfix;
    stack<string> 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<string>& postfix) {
    vector<Poly> 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] == '-' || all_of(begin(token), end(token),
                                           [](char c) { return isdigit(c); })) {
        polys.push_back(Poly("1", stoi(token)));
      } else {
        polys.push_back(Poly(token, 1));
      }
    return polys[0];
  }
};

			

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<String> toList() {
    List<String> res = new ArrayList<>();
    List<String> keys = new ArrayList<>(terms.keySet());
    Collections.sort(keys, new Comparator<String>() {
      @Override
      public int compare(final String a, final String b) {
        // Smallest degree is the last
        if (a.equals("1"))
          return 1;
        if (b.equals("1"))
          return -1;
        String[] as = a.split("\\*");
        String[] bs = b.split("\\*");
        // Largest degree is the first
        // Breaking ties by lexicographic order
        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<String, Integer> 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<String> basicCalculatorIV(String expression, String[] evalvars, int[] evalints) {
    List<String> tokens = getTokens(expression);
    Map<String, Integer> 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<String> postfix = infixToPostfix(tokens);
    return evaluate(postfix).toList();
  }

  private List<String> getTokens(final String s) {
    List<String> 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<String> infixToPostfix(List<String> tokens) {
    List<String> postfix = new ArrayList<>();
    Deque<String> 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<String> postfix) {
    LinkedList<Poly> 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();
  }
}

			

class Poly:
  def __init__(self, term: str = None, coef: int = None):
    if term and coef:
      self.terms = Counter({term: coef})
    else:
      self.terms = 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:
      # Smallest degree is the last
      if term == '1':
        return (0,)
      var = term.split('*')
      # Largest degree is the first
      # Breaking ties by lexicographic order
      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: chr, currOp: chr) -> 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]