# 如何实现一个计算器

Info

**已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~**

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode | Difficulty |
---|---|

224. Basic Calculator | 🔴 |

227. Basic Calculator II | 🟠 |

772. Basic Calculator III🔒 | 🔴 |

The calculator functionality we aim to implement is as follows:

Input a string that can contain

`+ - * /`

, numbers, parentheses, and spaces. Your algorithm should return the result of the computation.The operations should follow the rules of arithmetic, with the highest priority for parentheses, followed by multiplication and division, and then addition and subtraction.

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

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:

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.

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

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:

First, add a default

`+`

sign to the first number, turning it into`+1-12+3`

.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.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 the expression
// 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 formula
# 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 the formula
// 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 perform division
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 stack
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 stack
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.