So far, we have encountered the following series of calculator problems:\n\n1. [224. Basic Calculator](https://leetcode.com/problems/basic-calculator/description/)\n2. [227. Basic Calculator II](https://leetcode.com/problems/basic-calculator-ii/description/)\n3. [772. Basic Calculator III](https://leetcode.com/problems/basic-calculator-iii/description/)\n4. [770. Basic Calculator IV](https://leetcode.com/problems/basic-calculator-iv/description/)\n\nThough each of them may be solved using different methodologies, in this post I'd like to sort out the complexities and develop one "generic" solution to help us approach these problems.\n\nNote that this post is **NOT** intended to deal with general calculator problems that involve complicated operands/operators. The analyses below are limited to the scope as specified by the problem descriptions of the above four problems. \n\n---\n\n`I -- Definitions and terminology`\n\nIn this section I will spell out some definitions to facilitate the explanation.\n\n* `Expression`: An expression is a string whose value is to be calculated. Every expression must be alternating between **operand**s and **operator**s.\n\n* `Operand`: An operand is a "generalized value" that can be the target of an operator. It must be one of the following three types -- **number**, **variable**, **subexpression**.\n\n* `Number`: A number consists of digits only. The value of an operand of this type is given by the literal value of the number.\n\n* `Variable`: A variable consists of lowercase letters only. It can be either a free variable whose value is unknown, or a bound variable whose value is mapped to some number (can be looked up). Here we define the value of an operand of free variable type is given by the variable itself, while that of bound variable type is given by the value of the number to which the variable is mapped.\n\n* `Subexpression`: A subexpression is a valid expression enclosed in parentheses (which implies a recursive definition back to `Expression`). The value of an operand of this type is given by the calculated value of the subexpression itself.\n\n* `Operator`: An operator is some prescribed action to be taken on the target operands. It must be one of the following four types: `+`, `-`, `*`, `/`, corresponding to addition, subtraction, multiplication and integer division, respectively. Operators have precedences, where `+` and `-` have **level one** precedence, while `*` and `/` have **level two** precedence (the higher the level is, the higher the precedence is).\n\n---\n\n`II -- Rules for calculations`\n\nIn this section, I will specify the general rules for carrying out the actual evaluations of the expression.\n\n**Separation rule**:\n\n* We separate the calculations into two different levels corresponding to the two precedence levels.\n\n* For each level of calculation, we maintain two pieces of information: the *partial result* and the *operator in effect*. \n\n* For level one, the partial result starts from `0` and the initial operator in effect is `+`; for level two, the partial result starts from `1` and the initial operator in effect is `*`.\n\n* We will use `l1` and `o1` to denote respectively the partial result and the operator in effect for level one; `l2` and `o2` for level two. The operators have the following mapping: \n`o1 == 1` means `+`; `o1 == -1` means `-` ;\n`o2 == 1` means `*`; `o2 == -1` means `/`. \nBy default we have `l1 = 0`, `o1 = 1`, and `l2 = 1`, `o2 = 1`.\n\n**Precedence rule**:\n\n* Each operand in the expression will be associated with a precedence of level two by default, meaning they can only take part in calculations of precedence level two, not level one. \n\n* The operand can be any of the aforementioned types (number, variable or subexpression), and will be evaluated together with `l2` under the action prescribed by `o2`.\n\n**Demotion rule**:\n\n* The partial result `l2` of precedence level two can be demoted to level one. Upon demotion, `l2` becomes the operand for precedence level one and will be evaluated together with `l1` under the action prescribed by `o1`.\n\n* The demotion happens when either a level one operator (i.e., `+` or `-`) is hit or the end of the expression is reached. After demotion, `l2` and `o2` will be reset for following calculations.\n\n---\n\n`III -- Algorithm implementations`\n\nIn this section, I will lay out the general structure of the algorithm using pseudo-codes. From section `I`, we know there are at most five different types of structs contained in the expression: number, variable, subexpression, level one operators, level two operators. We will check each of them and proceed accordingly.\n\n```\npublic int calculate(String s) {\n int l1 = 0, o1 = 1; // Initialization of level one\n int l2 = 1, o2 = 1; // Initialization of level two\n \n for (int i = 0; i < s.length(); i++) {\n char c = s.charAt(i);\n \n if (c is a digit) {\n\n --> we have an operand of type number, so find its value "num"\n --> then evaluate at level two: l2 = (o2 == 1 ? l2 * num : l2 / num);\n \n } else if (c is a lowercase letter) {\n\n --> we have an operand of type variable, so find its name "var"\n --> then look up the variable mapping table to find its value "num";\n --> lastly evaluate at level two: l2 = (o2 == 1 ? l2 * num : l2 / num);\n\n } else if (c is an opening parenthesis) {\n\n --> we have an operand of type subexpression, so find its string representation\n --> then recursively call the "calculate" function to find its value "num";\n --> lastly evaluate at level two: l2 = (o2 == 1 ? l2 * num : l2 / num);\n \n } else if (c is a level two operator) {\n\n --> o2 needs to be updated: o2 = (c == '*' ? 1 : -1);\n\n } else if (c is a level one operator) {\n\n --> demotion happens here: l1 = l1 + o1 * l2;\n --> o1 needs to be updated: o1 = (c == '+' ? 1 : -1);\n --> l2, o2 need to be reset: l2 = 1, o2 = 1;\n\n }\n\n return (l1 + o1 * l2); // end of expression reached, so demotion happens again\n}\n```\n\n--- \n\n`IV -- List of solutions`\n\nIt is now straightforward to adapt the algorithm in section `III` to tackle each of the calculator problems. Note that not all the checks are needed for a particular version of the calculator problems. More specifically,\n\n* Basic Calculator I does not have variables and level two operators;\n\n* Basic Calculator II does not contain variables as well as subexpressions;\n\n* Basic Calculator III does not have variables;\n\n* Basic Calculator IV is the most general form but its level two operators do not include division (`/`).\n\nIn this section, I will list two solutions for Basic Calculator III (recursive and iterative), and one solution for Basic Calculator IV (recursive).\n\n---\n\n**Basic Calculator III**: Solutions for this version pretty much follow the general structure in section `III`, except that we do not need to check for variables since the input expression does not contain any.\n\n* Recursive solution: `O(n^2)` time, `O(n)` space\n\n```\npublic int basicCalculatorIII(String s) {\n int l1 = 0, o1 = 1;\n int l2 = 1, o2 = 1;\n \n for (int i = 0; i < s.length(); i++) {\n char c = s.charAt(i);\n \n if (Character.isDigit(c)) {\n int num = c - '0';\n \n while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {\n num = num * 10 + (s.charAt(++i) - '0');\n }\n \n l2 = (o2 == 1 ? l2 * num : l2 / num);\n \n } else if (c == '(') {\n int j = i;\n \n for (int cnt = 0; i < s.length(); i++) {\n if (s.charAt(i) == '(') cnt++;\n if (s.charAt(i) == ')') cnt--;\n if (cnt == 0) break;\n }\n \n int num = basicCalculatorIII(s.substring(j + 1, i));\n \n l2 = (o2 == 1 ? l2 * num : l2 / num);\n \n } else if (c == '*' || c == '/') {\n o2 = (c == '*' ? 1 : -1);\n \n } else if (c == '+' || c == '-') {\n l1 = l1 + o1 * l2;\n o1 = (c == '+' ? 1 : -1);\n\n l2 = 1; o2 = 1;\n }\n }\n \n return (l1 + o1 * l2);\n}\n```\n\n* Iterative solution: `O(n)` time, `O(n)` space\n\n```\npublic int basicCalculatorIII(String s) {\n int l1 = 0, o1 = 1;\n int l2 = 1, o2 = 1;\n\n Deque stack = new ArrayDeque<>(); // stack to simulate recursion\n\n for (int i = 0; i < s.length(); i++) {\n char c = s.charAt(i);\n\n if (Character.isDigit(c)) {\n int num = c - '0';\n\n while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {\n num = num * 10 + (s.charAt(++i) - '0');\n }\n\n l2 = (o2 == 1 ? l2 * num : l2 / num);\n\n } else if (c == '(') {\n // First preserve current calculation status\n stack.offerFirst(l1); stack.offerFirst(o1);\n stack.offerFirst(l2); stack.offerFirst(o2);\n \n // Then reset it for next calculation\n l1 = 0; o1 = 1;\n l2 = 1; o2 = 1;\n\n } else if (c == ')') {\n // First preserve the result of current calculation\n int num = l1 + o1 * l2;\n\n // Then restore previous calculation status\n o2 = stack.poll(); l2 = stack.poll();\n o1 = stack.poll(); l1 = stack.poll();\n \n // Previous calculation status is now in effect\n l2 = (o2 == 1 ? l2 * num : l2 / num);\n\n } else if (c == '*' || c == '/') {\n o2 = (c == '*' ? 1 : -1);\n\n } else if (c == '+' || c == '-') {\n l1 = l1 + o1 * l2;\n o1 = (c == '+' ? 1 : -1);\n\n l2 = 1; o2 = 1;\n }\n }\n\n return (l1 + o1 * l2);\n}\n```\n\n---\n\n**Basic Calculator IV**: Solutions for this version, however, require some extra effort apart from the general structure in section `III`. Due to the presence of variables (free variables, to be exact), the partial results for each level of calculations may not be pure numbers, but instead expressions (simplified, of course). So we have to come up with some structure to represent these partial results.\n\nThough multiple options exist as to designing this structure, we do want it to support operations like addition, subtraction and multiplication with relative ease. Here I represent each expression as a collection of mappings from terms to coefficients, where each term is just a list of free variables sorted in lexicographic order. Some quick examples:\n\n1. `"2 * a * b - d * c"`: this expression contains two terms, where the first term is `["a", "b"]` and the second is `["c", "d"]`. The former has a coefficient of `2` while the latter has a coefficient of `-1`. So we represent the expression as two mappings: `["a", "b"] --> 2` and `["c", "d"] --> -1`.\n\n2. "`4`": this expression contains a single term, where the term has **zero** free variables and thus will be written as `[]`. The coefficient is `4` so we have the mapping `[] --> 4`. More generally, for any expression formed only by a pure number `num`, we have `[] --> num`.\n\nSee below for a detailed definition of the `Term` and `Expression` classes. \n\nThe `Term` class will support operations for comparing two terms according to their degrees as well as for generating a customized string representation.\n\nThe `Expression` class will support operations for adding additional terms to the existing mapping.\n\n**Addition** of two expressions is done by adding all mappings in the second expression to those of the first one, and if possible, combine the coefficients of duplicate terms.\n\n**Subtraction** of two expressions is implemented by first negating the coefficients of terms in the second expression and then applying addition (and thus can be combined with addition).\n\n**Multiplication** of two expressions is done by collecting terms formed by merging every pair of terms from the two expressions (as well as their coefficients).\n\nLastly to conform to the format of the output, we have a dedicated function to convert the mappings in the result expression to a list of strings, where each string consists of the coefficient and the term connected by the `*` operator. Note that terms with `0` coefficient are ignored and terms without free variables contains numbers only.\n\nAs to complexity analysis, the nominal runtime complexity of this solution is similar to the recursive one for Basic Calculator III -- `O(n^2)`. It is also possible to use stacks to simulate the recursion process and cut the nominal time complexity down to `O(n)` (I will leave this as an exercise for you). \n\nHere I used the word "nominal" because the above analyses assumed that the addition, subtraction and multiplication operations of two expressions take constant time, as is the case when the expressions are pure numbers. Apparently this assumption no longer stands true, since the number of terms may grow exponentially (think about this expression `(a + b) * (c + d) * (e + f) * ...`). Nevertheless, this solution should work against average/general test cases.\n\n```\nprivate static class Term implements Comparable {\n List vars;\n static final Term C = new Term(Arrays.asList()); // this is the term for pure numbers\n\n Term(List vars) {\n this.vars = vars;\n }\n \n public int hashCode() {\n return vars.hashCode();\n }\n \n public boolean equals(Object obj) {\n if (this == obj) return true;\n \n if (!(obj instanceof Term)) return false;\n \n Term other = (Term)obj;\n \n return this.vars.equals(other.vars);\n }\n \n public String toString() {\n return String.join("*", vars);\n }\n \n public int compareTo(Term other) {\n if (this.vars.size() != other.vars.size()) {\n return Integer.compare(other.vars.size(), this.vars.size());\n } else {\n for (int i = 0; i < this.vars.size(); i++) {\n int cmp = this.vars.get(i).compareTo(other.vars.get(i));\n if (cmp != 0) return cmp;\n }\n }\n \n return 0;\n }\n}\n \nprivate static class Expression {\n Map terms;\n \n Expression(Term term, int coeff) {\n terms = new HashMap<>();\n terms.put(term, coeff);\n }\n \n void addTerm(Term term, int coeff) {\n terms.put(term, coeff + terms.getOrDefault(term, 0));\n }\n}\n\nprivate Term merge(Term term1, Term term2) {\n List vars = new ArrayList<>();\n \n vars.addAll(term1.vars);\n vars.addAll(term2.vars);\n Collections.sort(vars);\n \n return new Term(vars);\n}\n\nprivate Expression add(Expression expression1, Expression expression2, int sign) {\n for (Map.Entry e : expression2.terms.entrySet()) {\n expression1.addTerm(e.getKey(), sign * e.getValue());\n }\n \n return expression1;\n}\n\nprivate Expression mult(Expression expression1, Expression expression2) {\n Expression res = new Expression(Term.C, 0);\n \n for (Map.Entry e1 : expression1.terms.entrySet()) {\n for (Map.Entry e2 : expression2.terms.entrySet()) {\n res.addTerm(merge(e1.getKey(), e2.getKey()), e1.getValue() * e2.getValue());\n }\n }\n \n return res;\n}\n\nprivate Expression calculate(String s, Map map) {\n Expression l1 = new Expression(Term.C, 0);\n int o1 = 1;\n \n Expression l2 = new Expression(Term.C, 1); \n // we don't need 'o2' because the precedence level two operators contain '*' only\n \n for (int i = 0; i < s.length(); i++) {\n char c = s.charAt(i);\n \n if (Character.isDigit(c)) { // this is a number\n int num = c - '0';\n \n while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {\n num = num * 10 + (s.charAt(++i) - '0');\n }\n \n l2 = mult(l2, new Expression(Term.C, num));\n \n } else if (Character.isLowerCase(c)) { // this is a variable\n int j = i;\n \n while (i + 1 < s.length() && Character.isLowerCase(s.charAt(i + 1))) i++;\n \n String var = s.substring(j, i + 1);\n Term term = map.containsKey(var) ? Term.C : new Term(Arrays.asList(var));\n int num = map.getOrDefault(var, 1);\n \n l2 = mult(l2, new Expression(term, num));\n \n } else if (c == '(') { // this is a subexpression\n int j = i;\n \n for (int cnt = 0; i < s.length(); i++) {\n if (s.charAt(i) == '(') cnt++;\n if (s.charAt(i) == ')') cnt--;\n if (cnt == 0) break;\n }\n \n l2 = mult(l2, calculate(s.substring(j + 1, i), map));\n \n } else if (c == '+' || c == '-') { // level one operators\n l1 = add(l1, l2, o1);\n o1 = (c == '+' ? 1 : -1);\n \n l2 = new Expression(Term.C, 1);\n }\n }\n \n return add(l1, l2, o1);\n}\n\nprivate List format(Expression expression) {\n List terms = new ArrayList<>(expression.terms.keySet());\n \n Collections.sort(terms);\n \n List res = new ArrayList<>(terms.size());\n \n for (Term term : terms) {\n int coeff = expression.terms.get(term);\n \n if (coeff == 0) continue;\n \n res.add(coeff + (term.equals(Term.C) ? "" : "*" + term.toString()));\n }\n \n return res;\n}\n\npublic List basicCalculatorIV(String expression, String[] evalvars, int[] evalints) {\n Map map = new HashMap<>();\n \n for (int i = 0; i < evalvars.length; i++) {\n map.put(evalvars[i], evalints[i]);\n }\n \n return format(calculate(expression, map));\n}\n```

Basic Calculator III

Problem Description

Problem Description

Answer Panel