机试_3_数据结构（一）_习题

数据结构（一）——练习题

学习完第三章-数据结构（一）之后，当然要做相应地练习啦~

注：上述习题都可以在牛客进行测试。

例如，第2题链接：计算表达式_牛客题霸_牛客网 (nowcoder.com)，其他题目在“题目列表”中基本都可以找到。

另外，此文章仅仅是提供解题思路，并非最优解。

---

1、堆栈的使用–吉林大学

描述

堆栈是一种基本的数据结构。堆栈具有两种基本操作方式，push 和 pop。其中 push一个值会将其压入栈顶，而 pop 则会将栈顶的值弹出。现在我们就来验证一下堆栈的使用。（注：本题有多组输入，可以参考该网址：https://www.nowcoder.com/discuss/276）

输入描述：

对于每组测试数据，第一行是一个正整数 n（0 < n <= 10000）。而后的 n 行，每行的第一个字符可能是’P’或者’O’或者’A’；如果是’P’，后面还会跟着一个整数，表示把这个数据压入堆栈；如果是’O’，表示将栈顶的值 pop 出来，如果堆栈中没有元素时，忽略本次操作；如果是’A’，表示询问当前栈顶的值，如果当时栈为空，则输出’E’。堆栈开始为空。

输出描述：

对于每组测试数据，根据其中的命令字符来处理堆栈；并对所有的’A’操作，输出当时栈顶的值，每个占据一行，如果当时栈为空，则输出’E’。

示例1

输入：

3
A
P 5
A
4
P 3
P 6
O
A

输出：

E
5
3

题解：

#include <iostream>
#include <cstdio>
#include <stack>using namespace std;/*** 堆栈的使用* @return*/
int main() {int n;while (cin >> n) {stack<int> stack;for (int i = 0; i < n; ++i) {char instruction;cin >> instruction;if (instruction == 'P') {int num;cin >> num;stack.push(num);} else if (instruction == 'O') {if (!stack.empty()) {stack.pop();}} else {if (stack.empty()) {cout << "E" << endl;} else {cout << stack.top() << endl;}}}}return 0;
}

---

2、计算表达式–上海交通大学

描述

对于一个不存在括号的表达式进行计算

输入描述：

存在多组数据，每组数据一行，表达式不存在空格

输出描述：

输出结果

示例1

输入：

6/2+3+3*4

输出：

18

题解：

解题：
1. 在表达式的结尾加上"#"，表示结束符，然后从左到右遍历计算式
2. 若为操作数num，则压入操作数栈中
3. 若为运算符，则依次弹出运算符栈中比当前运算符优先级高的运算符；同时，依次弹出操作数栈中的元素（注意：先弹出的为右操作数）然后，执行相应的计算，将计算结果压入到操作数栈中。最后，将当前的运算符压入到运算符栈中。
4. 若为结束符"#"，依次弹出运算符栈中的运算符，依次弹出操作数栈中的元素，执行计算后将结果压入栈中
5. 最后栈中只剩一个元素，即为计算结果。

#include <iostream>
#include <cstdio>
#include <stack>
#include <string>
#include <map>using namespace std;/*** 计算运算符的操作结果* @param opera 运算符* @param leftNum 左操作数* @param rightNum 右操作数* @return*/
double calculate(char opera, double leftNum, double rightNum);/** map存放运算符的优先级*/
map<char, int> priority = {{'$', 0},{'+', 1},{'-', 1},{'*', 2},{'/', 2}
};/*** 计算表达式--上海交通大学* @return*/
int main() {string str;while (cin >> str) {/** 给表达式加上结束符*/str += "#";stack<char> operaStack;stack<double> numStack;string num = "";for (int i = 0; i < str.size(); ++i) {char cur = str[i];if (cur == '#') {/** 结束符* 1. 先将结束符#前面的num压入操作数栈中* 2. 依次弹出运算符栈中的运算符* 3. 依次弹出操作数栈中的操作符（注：先弹出的是右操作数）* 4. 执行相应计算，再将计算结构压入栈中*/if (num != "") {numStack.push(stod(num));num = "";}while (!operaStack.empty()) {char opera = operaStack.top();operaStack.pop();double rightNum = numStack.top();numStack.pop();double leftNum = numStack.top();numStack.pop();numStack.push(calculate(opera, leftNum, rightNum));}} else if ('0' <= cur && cur <= '9') {/** 0~9，将数字拼接到num中*/num += cur;} else {/** 操作符* 1. 先将操作符前面的num压入操作数栈中* 2. 依次弹出运算符栈中的运算符比当前运算符优先级高的运算符* 3. 依次弹出操作数栈中的操作符（注：先弹出的是右操作数）* 4. 执行相应计算，再将计算结构压入栈中* 5. 将当前的运算符压入运算符栈中*/if (num != "") {numStack.push(stod(num));num = "";}while (!operaStack.empty() && priority[operaStack.top()] >= priority[cur]) {char opera = operaStack.top();operaStack.pop();double rightNum = numStack.top();numStack.pop();double leftNum = numStack.top();numStack.pop();numStack.push(calculate(opera, leftNum, rightNum));}operaStack.push(cur);}}/** 此时，栈中有且只有一个元素，即为计算结果*/cout << numStack.top() << endl;}return 0;
}double calculate(char opera, double leftNum, double rightNum) {double res = 0;switch (opera) {case '+':res = leftNum + rightNum;break;case '-':res = leftNum - rightNum;break;case '*':res = leftNum * rightNum;break;case '/':res = leftNum / rightNum;break;default:break;}return res;
}

---