<p>Given an expression such as <code>expression = &quot;e + 8 - a + 5&quot;</code> and an evaluation map such as <code>{&quot;e&quot;: 1}</code> (given in terms of <code>evalvars = [&quot;e&quot;]</code> and <code>evalints = [1]</code>), return a list of tokens representing the simplified expression, such as <code>[&quot;-1*a&quot;,&quot;14&quot;]</code></p>

<ul>
	<li>An expression alternates chunks and symbols, with a space separating each chunk and symbol.</li>
	<li>A chunk is either an expression in parentheses, a variable, or a non-negative integer.</li>
	<li>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 <code>&quot;2x&quot;</code> or <code>&quot;-x&quot;</code>.</li>
</ul>

<p>Expressions are evaluated in the usual order: brackets first, then multiplication, then addition and subtraction.</p>

<ul>
	<li>For example, <code>expression = &quot;1 + 2 * 3&quot;</code> has an answer of <code>[&quot;7&quot;]</code>.</li>
</ul>

<p>The format of the output is as follows:</p>

<ul>
	<li>For each term of free variables with a non-zero coefficient, we write the free variables within a term in sorted order lexicographically.
	<ul>
		<li>For example, we would never write a term like <code>&quot;b*a*c&quot;</code>, only <code>&quot;a*b*c&quot;</code>.</li>
	</ul>
	</li>
	<li>Terms have degrees equal to the number of free variables being multiplied, counting multiplicity. We write the largest degree terms of our answer first, breaking ties by lexicographic order ignoring the leading coefficient of the term.
	<ul>
		<li>For example, <code>&quot;a*a*b*c&quot;</code> has degree <code>4</code>.</li>
	</ul>
	</li>
	<li>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.</li>
	<li>An example of a well-formatted answer is <code>[&quot;-2*a*a*a&quot;, &quot;3*a*a*b&quot;, &quot;3*b*b&quot;, &quot;4*a&quot;, &quot;5*c&quot;, &quot;-6&quot;]</code>.</li>
	<li>Terms (including constant terms) with coefficient <code>0</code> are not included.
	<ul>
		<li>For example, an expression of <code>&quot;0&quot;</code> has an output of <code>[]</code>.</li>
	</ul>
	</li>
</ul>

<p><strong>Note:</strong> You may assume that the given expression is always valid. All intermediate results will be in the range of <code>[-2<sup>31</sup>, 2<sup>31</sup> - 1]</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> expression = &quot;e + 8 - a + 5&quot;, evalvars = [&quot;e&quot;], evalints = [1]
<strong>Output:</strong> [&quot;-1*a&quot;,&quot;14&quot;]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> expression = &quot;e - 8 + temperature - pressure&quot;, evalvars = [&quot;e&quot;, &quot;temperature&quot;], evalints = [1, 12]
<strong>Output:</strong> [&quot;-1*pressure&quot;,&quot;5&quot;]
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> expression = &quot;(e + 8) * (e - 8)&quot;, evalvars = [], evalints = []
<strong>Output:</strong> [&quot;1*e*e&quot;,&quot;-64&quot;]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= expression.length &lt;= 250</code></li>
	<li><code>expression</code> consists of lowercase English letters, digits, <code>&#39;+&#39;</code>, <code>&#39;-&#39;</code>, <code>&#39;*&#39;</code>, <code>&#39;(&#39;</code>, <code>&#39;)&#39;</code>, <code>&#39; &#39;</code>.</li>
	<li><code>expression</code> does not contain any leading or trailing spaces.</li>
	<li>All the tokens in <code>expression</code> are separated by a single space.</li>
	<li><code>0 &lt;= evalvars.length &lt;= 100</code></li>
	<li><code>1 &lt;= evalvars[i].length &lt;= 20</code></li>
	<li><code>evalvars[i]</code> consists of lowercase English letters.</li>
	<li><code>evalints.length == evalvars.length</code></li>
	<li><code>-100 &lt;= evalints[i] &lt;= 100</code></li>
</ul>

struct string_hash {
  using is_transparent = void;
  [[nodiscard]] size_t operator()(const char *txt) const {
    return std::hash<std::string_view>{}(txt);
  }
  [[nodiscard]] size_t operator()(std::string_view txt) const {
    return std::hash<std::string_view>{}(txt);
  }
  [[nodiscard]] size_t operator()(const std::string &txt) const {
    return std::hash<std::string>{}(txt);
  }
};


using Symbol = std::variant<unsigned, int>;


template<class... Ts> struct overloaded : Ts... { using Ts::operator()...; };

template <typename T = Symbol>
using HeteroMap = std::unordered_map<std::string, T, string_hash, std::equal_to<>>;

inline bool isAlpha(const char& c) {
  return (c >= 'a') && (c <= 'z');
}

inline bool isNumeric(const char& c) {
  return (c >= '0') && (c <= '9');
}

class SymbolTable {
private:
  int freeSymbols { -1 };
  HeteroMap<Symbol> symbols {};

public:
  SymbolTable(std::string_view s, const HeteroMap<int>& evalMap) {
    std::set<std::string_view> nascent {};

    int current = 0;
    while (current < s.size()) {
      while (!isAlpha(s[current])) {
        ++current;
        if (current > s.size()) break;
      }

      int start = current++;
      while (current < s.size() && isAlpha(s[current])) {
        ++current;
      }

      if (start < s.size()) {
        nascent.insert(s.substr(start, current - start));
      }
    }

    unsigned rank = 0;
    for (const std::string_view& s: nascent) {
      auto it = evalMap.find(s);
      if (it != evalMap.end()) {
        symbols[std::string(s)] = it->second;
      }
      else {
        symbols[std::string(s)] = rank++;
      }
    }
    freeSymbols = rank;
  }

  int size() {
    return freeSymbols;
  }

  Symbol find(std::string_view sv) {
    return symbols.find(sv)->second;
  }

  std::vector<std::string_view> transpose() const {
    std::vector<std::string_view> trans(freeSymbols);
    for (const auto& [sv, sym]: symbols) {
      if(std::holds_alternative<unsigned>(sym)) {
        trans[std::get<unsigned>(sym)] = sv;
      }
    }

    return trans;
  }
};

class Monomial {
private:
  std::vector<uint_fast8_t> terms {};

public:
  int degree {0};
  Monomial(int n) {
    terms.resize(n);
    std::fill(terms.begin(), terms.end(), 0);
  }

  std::strong_ordering operator<=>(const Monomial& other) const {
    if (degree > other.degree) {
      return std::strong_ordering::less;
    }
    else if (other.degree > degree) {
      return std::strong_ordering::greater;
    }
    else {
      for (int i = 0; i < terms.size(); ++i) {
        if (terms[i] > other.terms[i]) {
          return std::strong_ordering::less;
        }
        else if (terms[i] < other.terms[i]) {
          return std::strong_ordering::greater;
        }
      }
    }
    return std::strong_ordering::equal;
  }

  void multiply(int i) {
    ++degree;
    ++terms[i];
  }

  friend Monomial operator*(const Monomial& a, const Monomial& b) {
    Monomial m (a.terms.size());
    m.degree = a.degree + b.degree;
    for (int i = 0; i < m.terms.size(); ++i) {
      m.terms[i] = a.terms[i] + b.terms[i];
    }
    return m;
  }

  std::string toString(const std::vector<std::string_view>& symbols) const {
    if (degree == 0) return "";
    std::string res {};

    int i;
    for (i = 0; i < terms.size(); ++i) {
      if (terms[i]) {
        res += symbols[i];
        for (int j = 1; j < terms[i]; ++j) {
          res += std::string("*") + std::string(symbols[i]);
        }
        break;
      }
    }

    ++i;
    for (; i < terms.size(); ++i) {
      for (int j = 0; j < terms[i]; ++j) {
        res += std::string("*") + std::string(symbols[i]);
      }
    }

    return res;
  }
};

class Polynomial {
private:
  std::map<Monomial, int> monomials {};


  template <typename Op>
  Polynomial& operate(const Polynomial&& other, Op op) {
    auto me = monomials.begin();
    auto them = other.monomials.begin();

    while (me != monomials.end() && them != other.monomials.end()) {
      std::strong_ordering relationship = me->first <=> them->first;
      if (relationship == std::strong_ordering::equal) {
        int n = op(me->second, them->second);
        if (n == 0) me = monomials.erase(me);
        else {
          me->second = n;
          ++me;
        }
        ++them;
      }
      else if (relationship == std::strong_ordering::greater) {
        monomials[std::move(them->first)] = op(0, them->second);
        ++them;
      }
      else {
        ++me;
      }
    }

    while (them != other.monomials.end()) {
      monomials[them->first] = op(0, them->second);
      ++them;
    };

    return *this;
  }

public:
  static Polynomial one(int symbols) {
    return Polynomial {1, Monomial{symbols}};
  }

  static Polynomial zero() {
    return Polynomial {};
  }

  Polynomial() {}

  Polynomial(int coeff, Monomial&& mono): monomials {{std::move(mono), coeff}} {}

  Polynomial& operator*=(const Polynomial& other) {

    std::map<Monomial, int> newMonomials {};

    for (const auto& [myBit, myCoeff]: monomials) {
      for (const auto& [theirBit, theirCoeff]: other.monomials) {
        Monomial mono = myBit * theirBit;
        auto it = newMonomials.find(mono);
        if (it == newMonomials.end()) {
          newMonomials[std::move(mono)] = myCoeff * theirCoeff;
        }
        else {
          int newCoeff = myCoeff * theirCoeff;
          if (it->second == -newCoeff) newMonomials.erase(it);
          else newMonomials[mono] += newCoeff;
        }
      }
    }

    monomials = std::move(newMonomials);
    return *this;
  }

  Polynomial& operator*=(const std::pair<int, Monomial> monomial) {
    std::map<Monomial, int> newMonomials;
    for (const auto& [myBit, myCoeff]: monomials) {
      newMonomials[myBit * monomial.second] = myCoeff * monomial.first;
    }

    monomials = std::move(newMonomials);
    return *this;
  }

  Polynomial& operator+=(const Polynomial&& other) {
    return operate(std::move(other), std::plus{});
  }

  Polynomial& operator-=(const Polynomial&& other) {
    return operate(std::move(other), std::minus{});
  }

  std::vector<std::string> toVector(const SymbolTable& symbols) {
    if (monomials.empty()) return {};

    std::vector<std::string_view> transpose = symbols.transpose();

    std::vector<std::string> res {};
    res.reserve(monomials.size());
    for (const auto& [mono, coeff]: monomials) {
      if (coeff == 0) continue;
      std::string newString { std::to_string(coeff) };
      if (mono.degree != 0) newString += std::string("*") + mono.toString(transpose);
      res.push_back(newString);
    }

    return res;
  }
};

class BasicCalculatorIV {
private:
  const std::string_view expression;
  SymbolTable symbols;
  int head = 0;

  inline char peek(int amount = 0) {
    return expression[head + amount];
  }

  inline void takeSpace() {
    if (!finished() && peek() == ' ') {
      advance();
    }
  }

  void advance(int amount = 1) {
    head += amount;
  }

  inline bool finished() {
    return head >= expression.size();
  }

  inline void match(char c) {
    // if (expression[head] != c) {
    //   std::cerr << "tried to match " << c << " but found instead " << expression[head] << "\n";
    //   exit(1);
    // }
    ++head;
  }

  Symbol parseSymbol() {
    int start = head;
    while (head < expression.size() && isAlpha(expression[head])) {
      ++head;
    }
    Symbol sym = symbols.find(expression.substr(start, head - start));
    takeSpace();
    return sym;
  }

  int parseInteger() {
    int res = 0;
    int m = 1;
    if (peek() == '-') {
      m = -1;
      advance();
    }

    while(isNumeric(peek())) {
      res *= 10;
      res += peek() - '0';
      advance();
    }
    takeSpace();
    return m * res;
  }

  std::pair<int, Monomial> parseMonomial() {
    Monomial myMonomial(symbols.size());
    int coeff = 1;
    char current = peek();

    while (isNumeric(current) || (current == '-' && peek(1) != ' ') || isAlpha(current)) {
      if (isAlpha(current)) {
        std::visit(overloaded {
          [&myMonomial](unsigned id) { myMonomial.multiply(id); },
          [&coeff](int val) { coeff *= val; },
          [](std::monostate) { __builtin_unreachable(); }
        }, parseSymbol());
      }
      else coeff *= parseInteger();

      takeSpace();
      if (peek() == '*') {
        advance();
        match(' ');
      }

      current = peek();
    }
    return {coeff, myMonomial};
  };

  Polynomial parseFactor() {

    Polynomial res = Polynomial::one(symbols.size());


    while (!finished() && peek() != '+' && peek() != '-' && peek() != ')') {
      if(peek() == '(') {
        advance();
        res *= parseExpression();
        match(')');
      }
      else {
        res *= parseMonomial();
      }

      takeSpace();
      if (peek() == '*') {
        advance();
        match(' ');
      }
    }

    return res;
  }

  Polynomial parseExpression() {

    Polynomial res = parseFactor();
    while (!finished() && peek() != ')') {
      if (peek() == '+') {
        advance();
        match(' ');
        res += parseFactor();
      }
      else if (peek() == '-') {
        advance();
        match(' ');
        res -= parseFactor();
      }
      else {
        std::cerr << "*screams*\n";
        __builtin_unreachable();
      }
      if (!finished() && peek() == ' ') advance();
    }
    return res;
  }

public:
  BasicCalculatorIV(const std::string& expression, const HeteroMap<int>& evalMap):
    expression{expression}, symbols{expression, evalMap} {}

  std::vector<std::string> go() {
    return parseExpression().toVector(symbols);
  }
};

class Solution {
public:
  static std::vector<std::string> basicCalculatorIV(const std::string& expression, const std::vector<std::string>& evalvars, const std::vector<int>& evalints) {
    HeteroMap<int> evalMap {};
    for (int i = 0; i < evalvars.size(); ++i) {
      evalMap[evalvars[i]] = evalints[i];
    }
    return BasicCalculatorIV(expression, evalMap).go();
  }
};
22900