字符串转整数
1
2
3
4
5
6
7
string s = "458";
int n = 0;
for (int i = 0; i < s.size(); i++) {
char c = s[i];
n = 10 * n + (c - '0');
}
// n 现在就等于 458
坑： (c -‘0’) 的这个括号不能省略，否则可能造成整型溢出。
因为变量 c 是⼀个 ASCII 码，如果不加括号就会先加后减，想象⼀下 s 如果接近 INT_MAX，就会溢出。所以⽤括号保证先减后加才⾏。
处理加减法
拿字符串算式 1-12+3 为例，来说⼀个很简单的思路：
- 先给第⼀个数字加⼀个默认符号 + ，变成
+1-12+3。 - 把⼀个运算符和数字组合成⼀对，也就是三对
+1，-12，+3，把它们转化成数字，然后放到⼀个栈中。 - 将栈中所有的数字求和，就是原算式的结果。
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
int calculate(string s) {
stack<int> stk;
// 记录算式中的数字
int num = 0;
// 记录 num 前的符号，初始化为 +
char sign = '+';
for (int i = 0; i < s.size(); i++) {
char c = s[i];
// 如果是数字，连续读取到 num
if (isdigit(c))
num = 10 * num + (c - '0');
// 如果不是数字，就是遇到了下⼀个符号，
// 之前的数字和符号就要存进栈中
if (!isdigit(c) || i == s.size() - 1) {
switch (sign) {
case '+':
stk.push(num); break;
case '-':
stk.push(-num); break;
}
// 更新符号为当前符号，数字清零
sign = c;
num = 0;
}
}
// 将栈中所有结果求和就是答案
int res = 0;
while (!stk.empty()) {
res += stk.top();
stk.pop();
}
return res;
}
处理乘除法
拿字符串 2-3*4+5 举例，核⼼思路依然是把字符串分解成符号和数字的组合。
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
for (int i = 0; i < s.size(); i++) {
char c = s[i];
if (isdigit(c))
num = 10 * num + (c - '0');
if (!isdigit(c) || i == s.size() - 1) {
switch (sign) {
int pre;
case '+':
stk.push(num); break;
case '-':
stk.push(-num); break;
// 只要拿出前⼀个数字做对应运算即可
case '*':
pre = stk.top();
stk.pop();
stk.push(pre * num);
break;
case '/':
pre = stk.top();
stk.pop();
stk.push(pre / num);
break;
}
// 更新符号为当前符号，数字清零
sign = c;
num = 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
static int start;
public static int calculate(String s) {
start = 0;
return calculateInner(s);
}
public static int calculateInner(String s) {
int num = 0;
char sign = '+';
Stack<Integer> stk = new Stack<>();
for (; start < s.length(); start++) {
char c = s.charAt(start);
if (Character.isDigit(c)) {
num = num * 10 + (c - '0');
}
if (c == '(') {
start++;
num = calculateInner(s);
}
if (c == ' ' && start != (s.length() - 1)) {
continue;
}
if (!Character.isDigit(c) || start == (s.length() - 1)) {
switch (sign) {
case '+':
stk.push(num);
break;
case '-':
stk.push(-num);
break;
case '*':
stk.push(num * stk.pop());
break;
case '/':
stk.push(stk.pop() / num);
break;
}
num = 0;
sign = c;
}
if (sign == ')') {
break;
}
}
int ret = 0;
while (!stk.empty()) {
ret += stk.pop();
}
return ret;
}
