How to Implement a Calculator

The calculator functionality we aim to implement is as follows:

1. Input a string that can contain + - * /, numbers, parentheses, and spaces. Your algorithm should return the result of the computation.

2. The operations should follow the rules of arithmetic, with the highest priority for parentheses, followed by multiplication and division, and then addition and subtraction.

3. Division should be integer division, rounding towards zero regardless of sign (5/2=2, -5/2=-2).

4. You can assume that the input expression is always valid, and the computation process will not cause integer overflow or division by zero.

For example, given the input string, the algorithm will return 9:

  3 * (2 - 6 / (3 - 7))
= 3 * (2 - 6 / (-4))
= 3 * (2 - (-1))
= 9

As you can see, this is very close to the calculators we use in daily life. While we have all used calculators before, a simple thought about their algorithm implementation can be quite surprising:

1. To handle parentheses correctly, you need to compute the innermost parentheses first and then gradually simplify outward. This process is error-prone even when done manually, let alone in an algorithm.

2. Ensuring multiplication and division are done before addition and subtraction is easy to teach a child but might be challenging for a computer.

3. Spaces need to be handled. For aesthetic reasons, we often put spaces between numbers and operators, but during computation, these spaces must be ignored.

I remember many university data structure textbooks use calculators as examples when discussing stack data structures. However, to be honest, the explanations are often poor, discouraging many future computer scientists from learning these simple data structures.

So, in this article, we will discuss how to implement a fully functional calculator. The key is to break down the problem, divide and conquer, and tackle each part one by one. A few simple algorithm rules can handle extremely complex calculations, and this mindset can help you solve various complex problems.

Let's start by breaking down from the simplest problem.

1. Converting a String to an Integer

Yes, such a simple problem. First, tell me, how do you convert a string representation of a positive integer into an int type?

String s = "458";

int n = 0;
for (int i = 0; i < s.length(); i++) {
    char c = s.charAt(i);
    n = 10 * n + (c - '0');
}
// n is now equal to 458

std::string s = "458";

int n = 0;
for (int i = 0; i < s.length(); i++) {
    char c = s[i];
    n = 10 * n + (c - '0');
}
// n is now equal to 458

s = "458"

n = 0
for i in range(len(s)):
    c = s[i]
    n = 10 * n + (ord(c) - ord('0'))
# n is now equal to 458

s := "458"

n := 0
for i := 0; i < len(s); i++ {
    c := int(s[i] - '0')
    n = 10*n + c
}
// n is now equal to 458

var s = "458";

var n = 0;
for (var i = 0; i < s.length; i++) {
    var c = s.charAt(i);
    n = 10 * n + (c.charCodeAt(0) - '0'.charCodeAt(0));
}
// n is now equal to 458

This is quite simple, the usual routine. However, even though it's simple, there's still a pitfall: you can't omit the parentheses in (c - '0'), otherwise, it may cause integer overflow.

The variable c is an ASCII code. If you don't use parentheses, it will add before subtracting. Imagine if s is close to INT_MAX, it will overflow. So, parentheses ensure subtraction happens before addition.

2. Handling Addition and Subtraction

Now, let's go a step further. If the input equation only contains addition and subtraction, with no spaces, how would you calculate the result? Let's take the string equation 1-12+3 as an example and explain a very simple idea:

1. First, add a default + sign to the first number, turning it into +1-12+3.

2. Combine each operator with its number into a pair, resulting in three pairs +1, -12, +3. Convert these pairs into numbers and place them in a stack.

3. Sum all the numbers in the stack to get the result of the original equation.

Let's look at the code directly, along with a diagram to make it clear:

int calculate(String s) {
    Stack<Integer> stk = new Stack<>();
    // record the numbers in the expression
    int num = 0;
    // record the sign before num, initialize as +
    char sign = '+';
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        // if it's a digit, continuously read it into num
        if (Character.isDigit(c)) {
            num = 10 * num + (c - '0');
        }
        // if it's not a digit, it means we
        // encountered the next sign or the end of
        // then the previous number and sign should be pushed into the stack
        if (c == '+' || c == '-' || i == s.length() - 1) {
            switch (sign) {
                case '+':
                    stk.push(num); break;
                case '-':
                    stk.push(-num); break;
            }
            // update the sign to the current one, reset num to zero
            sign = c;
            num = 0;
        }
    }
    // sum up all the results in the stack to get the answer
    int res = 0;
    while (!stk.isEmpty()) {
        res += stk.pop();
    }
    return res;
}

int calculate(string s) {
    stack<int> stk;
    // record the numbers in the expression
    int num = 0; 
    // record the sign before num, initialize as +
    char sign = '+';  
    for (int i = 0; i < s.length(); i++) {
        char c = s[i];
        // if it's a digit, continuously read into num
        if (isdigit(c)) {
            num = 10 * num + (c - '0');
        }
        // if it's not a digit, it means encountering the next sign or the end of the expression
        // then the previous number and sign should be stored in the stack
        if (c == '+' || c == '-' || i == s.length() - 1) {
            switch (sign) {
                case '+':
                    stk.push(num); break;
                case '-':
                    stk.push(-num); break;
            }
            // update the sign to the current sign, reset the number to zero
            sign = c;
            num = 0;
        }
    }
    // sum all results in the stack to get the answer
    int res = 0;
    while (!stk.empty()) {
        res += stk.top();
        stk.pop();
    }
    return res;
}

def calculate(s):
    stk = []
    # record the numbers in the formula
    num = 0
    # record the sign before num, initialized to +
    sign = '+'
    for i in range(len(s)):
        c = s[i]
        # if it's a digit, read it continuously into num
        if c.isdigit():
            num = 10 * num + int(c)
        # if it's not a digit, then it means we've
        # encountered the next sign or the end of the
        # then the previous number and sign should be stored in the stack
        if c == '+' or c == '-' or i == len(s) - 1:
            if sign == '+':
                stk.append(num)
            elif sign == '-':
                stk.append(-num)
            # update the sign to the current sign and reset the number to zero
            sign = c
            num = 0
    # the answer is the sum of all results in the stack
    res = 0
    while stk:
        res += stk.pop()
    return res

func calculate(s string) int {
    // record the number in the expression
    var num int
    // final result
    var res int
    // record the sign before num, initialize to +
    var sign int = 1
    // stack initialization
    stk := stack.New()

    // start traversing s in order
    for i := 0; i < len(s); i++ {
        // if it's a digit, continuously read into num
        if isDigit(s[i]) {
            num = 10*num + int(s[i]-'0')
        }
        // if it’s not a digit, it means encountering the next sign or the end of the expression
        // then the previous number and sign should be stored in the stack
        if s[i] == '+' || s[i] == '-' || i == len(s)-1 {
            // store the number and sign in the stack
            if sign == 1 {
                stk.Push(num)
            } else if sign == -1 {
                stk.Push(-num)
            }
            // update the sign to the current sign, reset the number to zero
            num = 0
            if s[i] == '+' {
                sign = 1
            } else if s[i] == '-' {
                sign = -1
            }
        }
    }
    // sum all the results in the stack to get the answer
    for stk.Len() != 0 {
        res += stk.Pop().(int)
    }
    // return the result
    return res
}

// helper function, determine if a character is a digit
func isDigit(n byte) bool {
    if '0' <= n && n <= '9' {
        return true
    }
    return false
}

var calculate = function(s) {
    // declare an array to replace the original Java stack
    var stk = [];
    // record the numbers in the formula
    var num = 0;
    // record the sign before num, initialized as +
    var sign = '+';
    for (var i = 0; i < s.length; i++) {
        var c = s.charAt(i);
        // if it's a number, continuously read into num
        if (!isNaN(c)) {
            num = 10 * num + (c - '0');
        }
        // if it's not a number, it means we
        // encountered the next sign, or the end of
        // then the previous number and sign should be stored into the stack
        if (c === '+' || c === '-' || i === s.length - 1) {
            switch(sign) {
                case '+':
                    stk.push(num);
                    break;
                case '-':
                    stk.push(-num);
                    break;
            }
            // update the sign to the current sign, and reset the number to zero
            sign = c;
            num = 0;
        }
    }
    // summing all the results in the stack gives the answer
    var res = 0;
    while (stk.length !== 0) {
        res += stk.pop();
    }
    return res;
}

I guess the part with the switch statement might be a bit hard to understand. The variable i scans from left to right, with sign and num following it. When s[i] encounters an operator, the situation looks like this:

Therefore, based on the different cases of sign, choose the positive or negative sign for num and push it onto the stack. Then update sign and reset num to record the next pair of sign and number.

Also, note that not only encountering a new operator will trigger a push to the stack, but when i reaches the end of the expression (i == s.size() - 1), the previous number should also be pushed to the stack to facilitate the final calculation of the result.

At this point, the algorithm for handling compact addition and subtraction strings is complete. Make sure you understand the above content, as the following content is just modifications based on this framework.

3. Handling Multiplication and Division

Actually, the idea is not much different from handling only addition and subtraction. Take the string 2-3*4+5 as an example, the core idea is still to break the string into pairs of operators and numbers.

For example, the above example can be broken down into +2, -3, *4, +5. We didn't handle multiplication and division just now, but it's simple. No other parts need to change, just add the corresponding cases in the switch part:

int calculate(String s) {
    Stack<Integer> stk = new Stack<>();
    // record the numbers in the formula
    int num = 0;
    // record the sign before num, initialized as +
    char sign = '+';
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (Character.isDigit(c)) {
            num = 10 * num + (c - '0');
        }

        if (c == '+' || c == '-' || c == '/' || c == '*' || i == s.length() - 1) {
            int pre;
            switch (sign) {
                case '+':
                    stk.push(num); break;
                case '-':
                    stk.push(-num); break;
                // just take out the previous number and perform corresponding operation
                case '*':
                    pre = stk.pop();
                    stk.push(pre * num);
                    break;
                case '/':
                    pre = stk.pop();
                    stk.push(pre / num);
                    break;
            }
            // update the sign to the current sign, reset the number to zero
            sign = c;
            num = 0;
        }
    }
    // sum up all the results in the stack to get the answer
    int res = 0;
    while (!stk.isEmpty()) {
        res += stk.pop();
    }
    return res;
}

int calculate(string s) {
    stack<int> stk;
    // record the numbers in the formula
    int num = 0;
    // record the sign before num, initialized to +
    char sign = '+';
    for (int i = 0; i < s.length(); i++) {
        char c = s[i];
        if (isdigit(c)) {
            num = 10 * num + (c - '0');
        }

        if (c == '+' || c == '-' || c == '/' || c == '*' || i == s.length() - 1) {
            int pre;
            switch (sign) {
                case '+':
                    stk.push(num); break;
                case '-':
                    stk.push(-num); break;
                // just take out the previous number for the corresponding operation
                case '*':
                    pre = stk.top(); stk.pop();
                    stk.push(pre * num);
                    break;
                case '/':
                    pre = stk.top(); stk.pop();
                    stk.push(pre / num);
                    break;
            }
            // update the sign to the current sign, reset the number to zero
            sign = c;
            num = 0;
        }
    }
    // summing up all the results in the stack gives the answer
    int res = 0;
    while (!stk.empty()) {
        res += stk.top(); stk.pop();
    }
    return res;
}

def calculate(s: str) -> int:
    stk = []
    # record the numbers in the equation
    num = 0
    # record the sign before num, initialized as +
    sign = "+"

    for i in range(len(s)):
        if s[i].isdigit():
            num = 10 * num + int(s[i])

        # encounter +,-,*,/ or reach the end
        if s[i] in "+-*/" or i == len(s) - 1:
            if sign == "+":
                stk.append(num)
            elif sign == "-":
                stk.append(-num)
            # just take out the previous number and perform the corresponding operation
            elif sign == "*":
                stk[-1] *= num
            else:
                # encounter division sign, need to
                # take out the previous number and
                stk[-1] = int(stk[-1] / num)

            # update the sign to the current sign, reset the number to zero
            sign = s[i]
            num = 0

    # sum all results in the stack to get the answer
    return sum(stk)

func calculate(s string) int {
  // initialize stack stk
  stk := make([]int, 0)
  // record numbers in the expression
  num := 0
  // record the sign before num, initialized to +
  sign := '+'
  
  for i, c := range s {
    if unicode.IsDigit(c) {
      num = 10*num + int(c-'0')
    }
    
    if c=='+' || c=='-' || c=='/' || c=='*' || i==len(s)-1 {
      var pre int
      switch sign {
      case '+':
        // if the sign is +, push the number onto the stack
        stk = append(stk, num)
      case '-':
        // if the sign is -, push the negated number onto the stack
        stk = append(stk, -num)
      case '*':
        // if the sign is *, pop the top element of the stack, multiply
        // it by the current number, and push the result back onto the
        pre = stk[len(stk)-1]
        stk = stk[:len(stk)-1]
        stk = append(stk, pre*num)
      case '/':
        // if the sign is /, pop the top element of the stack, divide
        // it by the current number, and push the result back onto the
        pre = stk[len(stk)-1]
        stk = stk[:len(stk)-1]
        stk = append(stk, pre/num)
      }
      // update the sign to the current sign, and reset the number to 0
      sign = rune(c)
      num = 0
    }
  }
  // sum all the results in the stack to get the answer
  res := 0
  for _, v := range stk {
    res += v
  }
  
  return res
}

var calculate = function(s) {
    var stack = [];
    // record the numbers in the formula
    var num = 0;
    // record the sign before num, initialized to +
    var sign = '+';
    for (var i = 0; i < s.length; i++) {
        var c = s[i];
        if (!isNaN(c)) {
            num = 10 * num + (c - '0');
        }

        if (c === '+' || c === '-' || c === '/' || c === '*' || i === s.length - 1) {
            var pre;
            switch (sign) {
                // just take out the previous number and perform the corresponding operation
                case '+':
                    stack.push(num); break;
                case '-':
                    stack.push(-num); break;
                case '*':
                    pre = stack.pop();
                    stack.push(pre * num); 
                    break;
                case '/':
                    pre = stack.pop();
                    stack.push(Math.trunc(pre / num));
                    break;
            }
            // update the sign to the current sign, and reset the number to zero
            sign = c;
            num = 0;
        }
    }
    // sum all the results in the stack to get the answer
    var res = 0;
    while (stack.length !== 0) {
        res += stack.pop();
    }
    return res;
};

Multiplication and division have higher precedence than addition and subtraction, meaning they can combine with the top number on the stack, while addition and subtraction just push themselves onto the stack.

Now, let's consider how to handle spaces in the string. According to our current code, we don't need special handling for spaces. Notice the if condition: when the character c is a space, it is simply skipped.

Great, our algorithm can now correctly handle addition, subtraction, multiplication, and division, and it automatically ignores spaces. The next step is to ensure the algorithm correctly recognizes parentheses.