Skip to content

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<string> toList() {
    vector<string> res;
    vector<string> 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<string> as = split(a, '*');
      const vector<string> 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<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 (const auto it = evalMap.find(token); it != evalMap.cend())
        token = to_string(it->second);

    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] == '-' ||
                 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<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) {
        // 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<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();
  }
}

  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]