腾讯面试手撕计算器，带括号和加减乘除的中缀表达式，面试的时候没有写出来，必须得学学咋做了。
前置知识
我们平时遇到的数学表达式其实都是中缀表达式，比如1+2/3这一类。但是对于计算机而言，计算后缀表达式是更加方便的操作，包括我们自己写计算的函数，也是后缀表达式更加好处理。
所以我们应该先记住中缀、后缀、前缀表达式的区别，以及如何将中缀表达式转为后缀表达式。因为选择题有时候也会考相关的题目，不仅是要会写代码，还得记住怎么人工转换。
我当时面试的时候就是忘记怎么把中缀转为后缀了，结果一直在死算，手撕给的时间本来就不多，临时写之前没写过的代码实在是写不出来，一堆BUG，突出一个菜。
这部分内容都在本站的另外一篇博客 逆波兰表达式求值 中有提到，本文不再重复。阅读本文之前，建议先阅读该文章并完成 leetcode 150.逆波兰表达式求值那道题。后缀表达式求值的思路如下：
- 从左往右遍历，遇到操作数，入栈；
- 遇到运算符，取栈顶两个连续数据进行计算（第二个取出来的是左操作数），再将计算结果入栈；
下面给出的是逆波兰表达式求值的代码。
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
| class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> s;
map<string,function<int(int,int)>> FuncMap = {
{"+",[](int x,int y){return x+y;}},
{"-",[](int x,int y){return x-y;}},
{"*",[](int x,int y){return x*y;}},
{"/",[](int x,int y){return x/y;}}
};
for(auto& ch : tokens)
{
if(ch=="+"||ch=="-"||ch=="*"||ch=="/")
{
int right=s.top();
s.pop();
int left=s.top();
s.pop();
int ret = FuncMap[ch](left,right);
s.push(ret);
}
else{
s.push(stoi(ch));
}
}
return s.top();
}
};
|
题目一：227. 基本计算器 II
227. 基本计算器 II 和 面试题 16.26. 计算器
这是leetcode上和计算器有关的题目中最简单的一个，它并不需要我们将中缀表达式转为后缀，直接通过一个栈加遍历的方式就可以将其写出来。
1
2
3
| 给定一个包含正整数、加(+)、减(-)、乘(*)、除(/)的算数表达式(括号除外)，计算其结果。
表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格。 整数除法仅保留整数部分。
|
代码如下，我们需要一个栈来存放处理的数字，并用一个num来拼接字符串里面的数字（虽然用例都是一位数字，但是题目并没有说不会出现多位数字，所以需要拼接），和一个prevClac指代上一个操作符。
当遇到操作符且不为空格，或者当前已经遍历到字符串末尾的时候，就需要进行计算。其他情况都说明是数字，对num变量进行拼接就可以了。
在计算过程中，我们把加减计算给替代成用数字的正负号来处理，乘除计算则直接对栈内元素做处理。这里需要记住一个小知识点，即STL的stack.top()函数返回的是栈顶元素的引用，所以我们可以直接对其进行修改，不需要用临时变量来处理。
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
| class Solution {
public:
bool isNum(char& c) { return c >= '0' && c <= '9'; }
int calculate(string s) {
stack<int> numSt;
int num = 0;
char prevClac = '+';
for (int i = 0; i < s.size(); i++) {
char& c = s[i];
if (isNum(c)) {
num = num * 10 + int(c - '0');
}
if ((!isNum(c) && c != ' ') || i == s.size() - 1) {
if (prevClac == '+') {
numSt.push(num);
} else if (prevClac == '-') {
numSt.push(-num);
}
else if (prevClac == '*') {
numSt.top() *= num;
} else if (prevClac == '/') {
numSt.top() /= num;
}
prevClac = c;
num = 0;
}
}
int sum = 0;
while (!numSt.empty()) {
sum += numSt.top();
numSt.pop();
}
return sum;
}
};
|
题目二：224. 基本计算器
https://leetcode.cn/problems/basic-calculator/description/
这道题在原本的普通中缀表达式的基础上，添加了括号，但没有乘除法。
我们可以用中缀表达式先转为后续表达式的方式，再使用上文提到过的150逆波兰表达式求值的代码来计算它。
题目
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
1
2
3
4
5
6
7
8
9
10
11
| 示例 1：
输入：s = "1 + 1"
输出：2
示例 2：
输入：s = " 2-1 + 2 "
输出：3
示例 3：
输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23
|
提示
1
2
3
4
5
6
7
| 1 <= s.length <= 3 * 105
s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
s 表示一个有效的表达式
'+' 不能用作一元运算(例如， "+1" 和 "+(2 + 3)" 无效)
'-' 可以用作一元运算(即 "-1" 和 "-(2 + 3)" 是有效的)
输入中不存在两个连续的操作符
每个数字和运行的计算将适合于一个有符号的 32位 整数
|
中缀表达式转后缀表达式
使用一个栈来存放操作符，注意左右括号，左括号的优先级低于任何操作符，右括号优先级高于任何操作符。
- 遇到操作数的时候 先输出 到结果表达式中;
- 遇到操作符，和栈顶进行比较
- 如果栈为空/操作符优先级高于栈顶，入栈；
- 操作符优先级低于栈顶或和栈顶相同，出栈顶操作符（然后继续比较当前操作符和栈顶操作符）；
- 如果是左括号
(，正常入栈； - 遇到右括号
)，出栈内所有操作符，直到遇到对应左括号，注意，最终的输出后缀表达式中不需要添加左/右括号； - 最后将栈中的操作符全部出栈，就可以获得后缀表达式；
具体的代码如下，有点长，但是不难理解
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
| #include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
bool isCalcHigher(const string& cur, const string& target)
{
if ((cur == "*" || cur == "/") && (target == "+" || target == "-"))
{
return true;
}
if (target == "(") {
return true;
}
return false;
}
vector<string> inOrderTobackOrder(const string& s)
{
vector<string> retV;
stack<string> st;
string num;
for (auto& itr : s)
{
string c;
c.push_back(itr);
if (c == " ")
{
continue;
}
if (c >= "0" && c <= "9")
{
num.push_back(c[0]);
continue;
}
if (num.size() > 0)
{
retV.push_back(num);
num.resize(0);
}
if (c == "(")
{
st.push(c);
}
else if (c == ")")
{
while (st.top() != "(")
{
retV.emplace_back(st.top());
st.pop();
}
st.pop();
}
else if (st.empty())
{
st.push(c);
}
else
{
if (isCalcHigher(c, st.top()))
{
st.push(c);
continue;
}
retV.emplace_back(st.top());
st.pop();
while (!st.empty() && !isCalcHigher(c, st.top()))
{
retV.emplace_back(st.top());
st.pop();
}
st.push(c);
}
}
if (num.size() > 0)
{
retV.push_back(num);
}
while (!st.empty())
{
retV.emplace_back(st.top());
st.pop();
}
return retV;
}
int main()
{
string s;
cout << "enter inOrder > ";
getline(cin, s);
auto retV = inOrderTobackOrder(s);
cout << "backOrder result: [";
for (int i = 0;i<retV.size();i++)
{
cout << "\"" << retV[i] << "\"";
if(i!=retV.size()-1){
cout << ", ";
}
}
cout << "]"<< endl;
return 0;
}
|
在224题目中给出的(1+(4+5+2)-3)+(6+8)这个表达式，经过转换的结果如下。
1
2
3
| ❯ g++ 中缀表达式转后缀表达式.cpp -o test && ./test
enter inOrder > (1+(4+5+2)-3)+(6+8)
backOrder result: ["1", "4", "5", "+", "2", "+", "+", "3", "-", "6", "8", "+", "+"]
|
把这个结果提供给150题目中的代码，计算结果就是23，代表我们的中缀转后缀的转换代码是正确的。
单独的正负号处理
有了这个函数后，我们就可以编写OJ的代码了，先把给出的中缀表达式转成后缀的，在进行计算。
先把基本的代码合并在一起，然后运行。此时会发现题目中有些刁钻的测试用例是过不了的。比如下面这个，它缺少了一个操作数，这导致我们中序转后续转出来的表达式是错误的。
题目中的提示也说明了这一点
1
2
| '+' 不能用作一元运算(例如， "+1" 和 "+(2 + 3)" 无效)
'-' 可以用作一元运算(即 "-1" 和 "-(2 + 3)" 是有效的)
|
这就需要我们对这种情况做个单独处理，即把-2变成0-2。
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
|
void stringHandler(string &s)
{
std::string tmp;
for (auto &c : s)
{
if (c != ' ')
{
tmp += c;
}
}
s.resize(0);
int n = tmp.length();
for (int i = 0; i < n; ++i)
{
if (tmp[i] == '-' && (i == 0 || tmp[i - 1] == '('))
{
s += "0-";
}
else if (tmp[i] == '+' && (i == 0 || tmp[i - 1] == '('))
{
s += "0+";
}
else
{
s += tmp[i];
}
}
}
|
可以看到，通过这个函数处理后，一切都正常了。
1
2
| enter inOrder > 1-( -2)
handle: 1-(0-2)
|
完整代码
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
| class Solution {
bool isCalcHigher(const string& cur, const string& target) {
if ((cur == "*" || cur == "/") && (target == "+" || target == "-")) {
return true;
}
if (target == "(") {
return true;
}
return false;
}
void stringHandler(string& s) {
std::string tmp;
for (auto& c : s) {
if (c != ' ') {
tmp += c;
}
}
s.resize(0);
int n = tmp.length();
for (int i = 0; i < n; ++i) {
if (tmp[i] == '-' && (i == 0 || tmp[i - 1] == '(')) {
s += "0-";
}
else if (tmp[i] == '+' && (i == 0 || tmp[i - 1] == '(')) {
s += "0+";
} else {
s += tmp[i];
}
}
}
vector<string> inOrderTobackOrder(string& s) {
vector<string> retV;
stack<string> st;
string num;
stringHandler(s);
for (auto& itr : s) {
string c;
c.push_back(itr);
if (c == " ") {
continue;
}
if (c >= "0" && c <= "9") {
num.push_back(c[0]);
continue;
}
if (num.size() > 0) {
retV.push_back(num);
num.resize(0);
}
if (c == "(") {
st.push(c);
}
else if (c == ")") {
while (st.top() != "(") {
retV.emplace_back(st.top());
st.pop();
}
st.pop();
}
else if (st.empty()) {
st.push(c);
} else
{
if (isCalcHigher(c, st.top())) {
st.push(c);
continue;
}
retV.emplace_back(st.top());
st.pop();
while (!st.empty() && !isCalcHigher(c, st.top())) {
retV.emplace_back(st.top());
st.pop();
}
st.push(c);
}
}
if (num.size() > 0) {
retV.push_back(num);
}
while (!st.empty()) {
retV.emplace_back(st.top());
st.pop();
}
return retV;
}
public:
int calculate(string s) {
auto retV = inOrderTobackOrder(s);
stack<int> st;
unordered_map<string, function<int(int, int)>> funcMap = {
{"+", [](int x, int y) { return x + y; }},
{"-", [](int x, int y) { return x - y; }},
{"*", [](int x, int y) { return x * y; }},
{"/", [](int x, int y) { return x / y; }}};
for (auto& ch : retV) {
if (ch == "+" || ch == "-" || ch == "*" || ch == "/") {
int right = st.top();
st.pop();
int left = st.top();
st.pop();
int ret = funcMap[ch](left, right);
st.push(ret);
} else {
st.push(stoi(ch));
}
}
return st.top();
}
};
|
题目三：772. 基本计算器 III
https://leetcode.cn/problems/basic-calculator-iii/
这道题和上一道题的区别就是多了乘法和除法。上一道题我们使用中缀转后缀再计算的思路已经包含了处理除法的情况了，所以直接用相同的代码就能过了。
腾讯面试的时候考的也是这道题，竟然在leetcode上需要开plus会员才能看，无语。
爱发电
