c++_栈习题
编排字符串
3575. 编排字符串 - AcWing题库
题目：请输入字符串，最多输出 4 个字符串，要求后输出的字符串排在前面
输入： 第一行为字符串个数 m。
接下来 m行：字符串s。
输出：
每有一行字符串的输入， 就要有1行的输出
对应有m行，每行：最多输出 4 个字符串
思路：
输出中要求后输出的字符串排在前面，故我们需要使用栈；
1)定义一个栈myStack；将输入的各个字符串压入其中
2）在每一个字符串输入之后，再定义另一个栈outputStack，接收当前myStack栈中的值，弹栈操作便在这个outStack中执行。（这样就能不破坏myStack的结构);
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include <stdio.h>
#include<string>
#include<stack>
using namespace std;
int main() {
int m;
scanf("%d", &m);
stack<string> myStack;
for (int i = 0; i < m; i++) {
string s;
char arr[1024];
scanf("%s", arr);
s = arr;
myStack.push(s);
stack<string>outputStack = myStack;
for (int j = 1; j <= 4; j++) {
if (outputStack.empty()) {
break;
}
printf("%d=%s ", j, outputStack.top().c_str());
outputStack.pop();
}
printf("\n");
}
return 0;
}代码分析
1.这道题最需要学习的是他的输入方式；即他是每输入一个字符串就需要打印一次；我们需要输入m个字符串；所以使用一个for(int i。。。。)循环，然后在该循环中进行处理+输出。
2.从输出样例我们可以看到，每一轮的输出过后栈的元素并没有被弹出；但是输出内容却又需要按照先进先出的形式在进行（即得先弹出上一个才能输出下一个），这种情况上面代码想到了什么工具？
==》使用一个副本 stack<string>outputStack在每一轮for(int i......)中来复制栈中的内容，弹栈的操作就由这个副本来进行。
括号匹配
输入： 共一行，包含一个由 <,(,{,[,>,),},] 构成的字符串。
输出：括号若正确匹配；则输出yes，否则输出no
处理：判断括号是否匹配
题目中有4种括号：
小括号： ( ) 中括号： [ ] 大括号： { } 尖括号： < >
对于一组括号来说： 左右括号的数量要相等，顺序要正确（左括号在前， 每个右括号要匹配最近的未匹配的左括号 ）具体来说：
对于([])
后面的[]符号需要优先匹配；所以我们可以借助栈的结构；我们可以这样做：
遇到左括号时压栈；遇到右括号弹栈；且如果有以下情况，便能说明括号不匹配
1）栈为空，遇到右边括号
2）栈非空，遇到右括号，但是左右括号不匹配；
3）扫描完字符串，栈非空（即存在还没匹配的左括号）
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<string>
#include<stack>
using namespace std;
/*判断当前字符属于左括号还是右括号
参数：字符
返回值：int
*/
int isWhat(char c) {
if (c == '<' || c == '(' || c == '{' || c == '[') {
return -1;
}
else if (c == '>' || c == ')' || c == '}' || c == ']') {
return -2;
}
else {
return -3;
}
}
bool isMatch(char left, char right) {
if (left == '(' && right == ')'
|| left == '<' && right == '>'
|| left == '{' && right == '}'
|| left == '[' && right == ']') {
return true;
}
else {
return false;
}
}
int main() {
string s;
char arr[10000];
scanf("%s", arr);
s = arr;
//定义一个栈
stack<char> myStack;
//扫描输入的字符串
for (int i = 0; i < s.size(); i++) {
//遇到左括号就输将之压栈
if (isWhat(s[i]) == -1) {
myStack.push(s[i]);
}
if (isWhat(s[i]) == -2) {
//右括号
//若栈为空，或当前扫描到的字符与栈顶的元素不匹配，则失败
if (myStack.empty() || !isMatch(myStack.top(), s[i])) {
printf("no");
return 0;
}
myStack.pop();
}
}
//最后判断栈中元素是否为空
if (!myStack.empty()) {
printf("no");
return 0;
}
printf("yes");
return 0;
}
计算表达式
输入：一个不含括号的表达式
输出：最终的值
处理：得出结果。
思路
以123+456-123/489*10为例
1.我们需要定义两个栈，运算符栈和操作数栈
2.当我们从左往右扫描运算符；当我们扫描到运算符之后不能立即计算他，我们得兼顾看后面的运算符，若后面的运算符优先级更高，我们得先算后面的（故我们可以使用一个栈来存储运算符）
例如上面先扫描到了+。我们先将+压栈{+}，再扫描到后面的运算符是-，因为-的运算符并不比+高，所以这是+便可以计算了，即可以从栈中弹出，再将-压栈，此时的栈便变成了{-}
3.操作时机
压栈：栈为空或新的运算符的优先级更高
弹栈：新的运算符的优先级更低
代码：
代码过程：
numStack 表示数字栈
opStack 表示运算符栈
循环扫描字符串：
1.当扫描到的字符是数字字符，就加入到字符串 numStr中，而后当扫描到非数字字符，就可以收网了。（即将前面的 numStr转为double,并压入数字栈中）
2.当扫描的是非数字字符（可能为运算符也可能已经到达字符串末尾）:
1)若!opStack.empty()&&priority[str[i]]<=priority[opStack.top()] 即运算符栈不为空且当前扫描到的运算符的优先级比栈顶的要低；我们要做的是：循环弹栈和计算（先弹出右操作数，再弹出左操作数，再将运算符弹出来，计算完成之后把结果再压入numStack 中）。
2）如果运算符栈为空或者前扫描到的运算符的优先级比栈顶的要高，则将这个运算符压栈。当然，如果是到了字符串的末尾，则直接打印numStack的元素（强制为整数）。并结束循环。
3.我们可以使用一个map结构来维持运算符的优先级。
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<string>
#include<stack>
#include<map>
using namespace std;
int main() {
//输入；一个不含括号的表达式
char str[1024] = { 0 };
//使用一个map结构来维持运算符的优先级
map<char, int> priority = {
{'\0',0}, {'+',1}, {'-',1},{'*',2}, {'/',2},
};
while(scanf("%s", str) != EOF) {
stack<char>opStack;
stack<double>numStack;
//提取数值
string numStr = "";
//遍历字符串
for (int i = 0;; i++) {
if (str[i] >= '0' && str[i] <= '9') {
numStr.push_back(str[i]);
}
else {
//读到的不是0-9字符，意味着前面读到的但就是0-9字符
double num = stod(numStr);
numStr = "";
//把数据识别出来后便压栈
numStack.push(num);
//什么时候弹栈 栈非空&&新op的优先级不高于栈顶的优先级
//循环弹栈和计算
while (!opStack.empty() && priority[str[i]] <= priority[opStack.top()]) {
//先弹出右操作数
double rhs = numStack.top();
numStack.pop();
//再弹出左操作数
double lhs = numStack.top();
numStack.pop();
//再将运算符弹出来
char curOp = opStack.top();
opStack.pop();
//计算
if (curOp == '+') {
numStack.push(lhs + rhs);
}
else if (curOp == '-') {
numStack.push(lhs - rhs);
}
else if (curOp == '*') {
numStack.push(lhs * rhs);
}
else if (curOp == '/') {
numStack.push(lhs / rhs);
}
}
//如果离开了这个循环，则说明栈悟空或新op的优先级高于栈顶
if (str[i] == '\0') {
printf("%d\n", (int)numStack.top());
break;
}
else {
opStack.push(str[i]);
}
}
}
}
return 0;
}代码分析
1.上面我们将字符串转为数字，不适用int，而使用double，为什么？
==》虽然整数int的加法和减法无影响，但整数的乘法和除法会存在数据丢失的问题；所以我们将数字字符转成double;
2.上述代码将for循环中判断循环是否成立的语句放到循环体中，这样有什么好处？
==》我们可以在里面写一些循环结束前的处理；例如在上面的循环中，再退出循环前,我们需要打印出结果（形式为整数）。
if (str[i] == '\0') {
printf("%d\n", (int)numStack.top());
break;
}2.我们来详细分析以下的代码：
char str[1024];
while (scanf("%s", str) != EOF) {
// 处理字符串
}1.scanf的行为 scanf("%s", str) 会读取输入中的字符串，直到遇到空白字符（如空格、换行符等）。 每次读取的字符串都会以 \0 结尾。 如果输入结束（例如文件结束或用户输入 Ctrl+D），scanf 会返回 EOF，循环结束。
2.字符数组最后的值：scanf("%s", str) 会在 str 的末尾自动添加 \0，这是 C 风格字符串的特性，只有用字符数组表示字符串时才会有这种情况。std::string 则不需要显式处理 \0。
3.如果我在最开始输入结束后，使用string s=str来接收，判断字符遍历接收的条件可以用：if(i==s.size())，如下所示：
// 如果离开了这个循环，则说明栈空或新op的优先级高于栈顶
if (i == s.size()) {
printf("%d\n", (int)numStack.top());
break;
} else {
opStack.push(s[i]);
}