The calculator problem is all about evaluating a mathematical expression. It is essentially a mini interpreter (including a lexer and a parser).

A general method to handle these problems is writing a mini interpreter from lexing, parsing, AST generation, and evaluation. However, it is still too much code for a technical interview, especially given the specific scenarios, lots of these codes will be redundant.

224. Basic Calculator

This problem includes parentheses, + and – operators. There is no negative operator and no * or / operators. The input is guaranteed to be well-formed.

Based on the conditions, we need to evaluate the subexpression inside parentheses independently by using stacks.

• Keep a stack of the intermediate results of the current expressions/subexpressions.
• Keep a stack of the operator of the expressions/subexpressions.

The strategy is evaluating from left to right.

Without parentheses, calculate the result with the left-hand side value (as the current result, from the top of the value stack), the operator (from the unvisited chars), and the right-hand side value (from the unvisited chars). Replace the top of the value stack with the calculated value (as the new current result).

At parentheses, push the operator and the initial value (0) to the stacks when we start a subexpression. Pop the operator and the final result from the stacks when we finish a subexpression.  Update the current result with the operator and the operand (which is the result of the subexpression) and move on.

227. Basic Calculator II

Compared to (1), this problem doesn’t include parentheses but includes * or / operators. The input is still guaranteed to be well-formed.

Based on the conditions, we need to evaluate the * or / operators firstly and the  + or – operator secondly by using lists. We can think all the expressions contain and only contains * or / operators as subexpressions. It is much similar to (2), but the expressions won’t be nested and we won’t need to use stacks.

772. Basic Calculator III

Compared to (1) and (2), this problem is the most common case. It includes * or / operators, includes parentheses and includes negative numbers.

The strategy is to keep two stacks, one as the numbers, the other as the operators, including ‘(‘ and ‘)’. Whenever we meet operators, we first clear the operator with higher precedence: pop the two operands from the number stack, one operator from the operator stack, do the calculation, and push the result to the number stack. We can keep doing this until there is no precedence. It is intrinsically evaluating the expressions in a bottom-up approach.

• For the + and – operators, the precedent calculations will be +, -, * and / operators on the left-hand side until parentheses.
• For the * and / operators, the precedent calculations will be * and / operators on the left-hand side until parentheses.

Besides, a the end of a pair of parentheses and at the end of the expression, we need to handle the uncleared calculation.

For negative numbers, simply keep a status mark, at the beginning of the expression, or a subexpression surrounded by parentheses, or right after an operator, the next minus operator must be a unary operator, in other words, the negative sign. We can simply add a zero before the sign, transferring -x to 0-x, making the minus operator as a binary operator again and follow the rules.

770. Basic Calculator IV

It is quite similar to (2). Except that the operands are polynomial terms instead of integers. The trick here is to design polynomial classes and add operator overloading. It is relatively easy to do in object-oriented languages, such as c++ / python.