C++中已经自带堆栈对象stack,无需编写堆栈操作的具体实现代码。
本题目主要帮助大家熟悉stack对象的使用,然后实现字符串的逆序输出
输入一个字符串,按字符按输入顺序压入堆栈,然后根据堆栈后进先出的特点,做逆序输出
stack类使用的参考代码
n包含头文件<stack>:#include <stack>
n创建一个堆栈对象s(注意stack是模板类):stack <char> ?s;//堆栈的数据类型是字符型
n把一个字符ct压入堆栈:s.push(ct);
n把栈顶元素弹出:s.pop();
n获取栈顶元素,放入变量c2:c2 =s.top();
n判断堆栈是否空:s.empty(),如果为空则函数返回true,如果不空则返回false
第一行输入t,表示有t个测试实例
第二起,每一行输入一个字符串,注意字符串不要包含空格
字符串的输入可以考虑一下代码:
#include <string>
int main()
{ string str;
Int len;
cin>>str; //把输入的字符串保存在变量str中
len = str.length()? //获取输入字符串的长度
}
每行逆序输出每一个字符串
样例查看模式?
正常显示查看格式
2
abcdef
aabbcc
fedcba
ccbbaa
#include<iostream>
#include<stack>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
string s;
cin >> s;
stack<char>st;
for (int i = 0; i < s.size(); i++)
{
st.push(s[i]);
}
while(!st.empty())
{
cout << st.top();
st.pop();
}
cout << endl;
}
return 0;
}
使用C++的STL堆栈对象,编写程序实现行编辑功能。行编辑功能是:当输入#字符,则执行退格操作;如果无字符可退就不操作,不会报错
本程序默认不会显示#字符,所以连续输入多个#表示连续执行多次退格操作
每输入一行字符打回车则表示字符串结束
注意:必须使用堆栈实现,而且结果必须是正序输出
第一行输入一个整数t,表示有t行字符串要输入
第二行起输入一行字符串,共输入t行
每行输出最终处理后的结果,如果一行输入的字符串经过处理后没有字符输出,则直接输出NULL
样例查看模式?
正常显示查看格式
4
chinaa#
sb#zb#u
##shen###zhen###
chi##a#####
china
szu
sz
NULL
1
###############################################################################################
NULL
#include<iostream>
#include<stack>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
string s;
cin >> s;
stack<char>st;
for (int i = 0; i < s.size(); i++)
{
if (s[i] != '#')st.push(s[i]);
else
{
if (!st.empty())
{
st.pop();
}
}
}
stack<char>ans;
while(!st.empty())
{
ans.push( st.top());
st.pop();
}
if (ans.empty())
{
cout << "NULL" << endl;
}
else
{
while (!ans.empty())
{
cout << ans.top();
ans.pop();
}
cout << endl;
}
}
return 0;
}
给出一个N*N的迷宫矩阵示意图,从起点[0,0]出发,寻找路径到达终点[N-1, N-1]
要求使用堆栈对象来实现,具体算法参考课本3.2.4节51页
第一行输入t,表示有t个迷宫
第二行输入n,表示第一个迷宫有n行n列
第三行起,输入迷宫每一行的每个方格的状态,0表示可通过,1表示不可通过
输入n行
以此类推输入下一个迷宫
逐个输出迷宫的路径
如果迷宫不存在路径,则输出no path并回车
如果迷宫存在路径,将路径中每个方格的x和y坐标输出,从起点到终点,每输出四个方格就换行,最终以单词END结尾,具体格式参考示范数据
输出的代码参考如下:
//path是保存路径的堆栈,堆栈中每个元素都包含x坐标和y坐标,用属性xp和yp表示
//path1是一个临时堆栈,把path的数据倒序输出到path1,使得路径按正序输出
if (!path.empty())//找到路径
{//......若干代码,实现path的数据导入path1
i=0; ?//以下是输出路径的代码
while (!path1.empty())
{cpos = path1.top();
if ( (++i)%4 == 0 )
cout<<'['<<cpos.xp<<','<<cpos.yp<<']'<<"--"<<endl;
else
cout<<'['<<cpos.xp<<','<<cpos.yp<<']'<<"--";
path1.pop();
}
cout<<"END"<<endl;
}
else
cout<<"no path"<<endl; //找不到路径输出no path
样例查看模式?
正常显示查看格式
2
8
0?0?0?1?1?1?1?1
1?0?0?0?1?0?0?1
1?0?0?0?1?0?0?0
1?1?0?0?0?0?0?1
0?0?1?1?0?1?1?0
0?0?0?0?0?0?1?1
1?1?1?1?1?0?0?1
0?0?0?0?1?0?0?0
7
0?0?0?1?1?1?1
1?0?0?1?0?0?1
1?0?0?1?0?0?0
1?1?0?0?0?0?1
0?0?1?1?0?1?0
1?0?0?0?0?1?0
0?0?0?0?1?1?0
[0,0]--[0,1]--[0,2]--[1,2]--
[1,3]--[2,3]--[3,3]--[3,4]--
[4,4]--[5,4]--[5,5]--[6,5]--
[6,6]--[7,6]--[7,7]--END
no?path
2
12
0?1?1?1?1?1?1?1?1?1?1?0
0?0?0?0?0?0?0?0?0?0?0?1
0?1?1?1?1?0?1?1?1?1?0?1
1?0?0?0?0?0?0?0?0?0?0?1
0?0?1?1?1?1?0?1?0?1?1?0
0?1?1?1?1?1?1?1?1?1?0?0
0?0?0?0?0?0?0?0?0?0?0?1
1?1?1?1?0?1?1?1?1?1?0?1
1?1?1?1?1?0?1?1?1?1?0?1
1?1?1?1?1?0?0?0?0?0?0?0
1?1?1?1?1?1?1?1?0?1?1?1
0?1?0?1?0?1?0?1?0?0?0?0
12
0?1?1?1?1?1?1?1?1?1?1?0
0?0?0?0?0?0?0?0?0?0?0?1
0?1?1?1?1?0?1?1?1?1?0?1
1?0?0?0?0?0?0?0?0?0?0?1
0?0?1?1?1?1?0?1?0?1?1?0
0?1?1?1?1?1?1?1?1?1?0?0
0?0?0?0?0?0?0?0?0?0?1?1
1?1?1?1?0?1?1?1?1?1?0?1
1?1?1?1?1?0?1?1?1?1?0?1
1?1?1?1?1?0?0?0?0?0?0?0
1?1?1?1?1?1?1?1?0?1?1?1
0?1?0?1?0?1?0?1?0?0?0?0
[0,0]--[1,0]--[1,1]--[1,2]--
[1,3]--[1,4]--[1,5]--[1,6]--
[1,7]--[1,8]--[1,9]--[1,10]--
[2,10]--[3,10]--[3,9]--[3,8]--
[3,7]--[3,6]--[3,5]--[3,4]--
[3,3]--[3,2]--[3,1]--[4,1]--
[4,0]--[5,0]--[6,0]--[6,1]--
[6,2]--[6,3]--[6,4]--[6,5]--
[6,6]--[6,7]--[6,8]--[6,9]--
[6,10]--[7,10]--[8,10]--[9,10]--
[9,9]--[9,8]--[10,8]--[11,8]--
[11,9]--[11,10]--[11,11]--END
no?path
#include<iostream>
#include<stack>
#include<vector>
using namespace std;
void GoMaze(int n)
{
//vector开二维数组
vector<vector<int>>g(n, vector<int>(n));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin>> g[i][j];
}
}
//起点和终点不通
if (g[0][0] == 1 || g[n - 1][n - 1] == 1)
{
cout << "no path" << endl;
return;
}
stack<pair<int, int>>path;
int x = 0, y = 0;
bool flag = 0;
path.push({ x,y });
while (!path.empty())
{
g[x][y] = 1;//走过不再走
if (y + 1 <= n - 1 && g[x][y + 1] == 0)//先向下
{
y++;
path.push({ x,y });
}
else if (x + 1 <= n - 1 && g[x + 1][y] == 0)//再向右
{
x++;
path.push({ x,y });
}
else if (y - 1 >= 0 && g[x][y - 1] == 0)//向上退回
{
y--;
path.push({ x,y });
}
else if (x - 1 >= 0 && g[x - 1][y] == 0)//向左退回
{
x--;
path.push({ x,y });
}
else
{
//不能前进也无法退回(例如)
//---1
//11-1
//1111
//退回原来的位置,再次选择
path.pop();//此位置不行
if (!path.empty())//每次pop前都要判断,预防报错
{
auto tt = path.top();//使用栈体现,刚刚走过的
x = tt.first;
y = tt.second;
}
}
if (x == n - 1 && y == n - 1)
{
flag = 1;
break;
}
}
if (flag)
{
stack<pair<int, int>>temp;
while (!path.empty())
{
temp.push(path.top());
path.pop();
}
int count = 0;
while (!temp.empty())
{
cout << "[" << temp.top().first << "," << temp.top().second << "]";
count++;
temp.pop();
cout << "--";
if (count == 4)
{
count = 0;
cout << endl;
}
}
cout << "END" << endl;
}
else
{
cout << "no path" << endl;
}
}
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
GoMaze(n);
}
return 0;
}
处理表达式过程中需要对括号匹配进行检验,括号匹配包括三种:“(”和“)”,“[”和“]”,“{”和“}”。例如表达式中包含括号如下:
( ) [ ( ) ( [ ] ) ] { }
1 2 3 4 5 6 7 8 9 10 11 12
从上例可以看出第1和第2个括号匹配,第3和第10个括号匹配,4和5匹配,6和9匹配,7和8匹配,11和12匹配。从中可以看到括号嵌套的的情况是比较复杂的,使用堆栈可以很方便的处理这种括号匹配检验,可以遵循以下规则:
1、 当接收第1个左括号,表示新的一组匹配检查开始;随后如果连续接收到左括号,则不断进堆栈。
2、 当接受第1个右括号,则和最新进栈的左括号进行匹配,表示嵌套中1组括号已经匹配消除
3、 若到最后,括号不能完全匹配,则说明输入的表达式有错
建议使用C++自带的stack对象来实现
stack类使用的参考代码
n包含头文件<stack>:#include <stack>
n创建一个堆栈对象s(注意stack是模板类):stack <char> ?s;//堆栈的数据类型是字符型
n把一个字符ct压入堆栈:s.push(ct);
n把栈顶元素弹出:s.pop();
n获取栈顶元素,放入变量c2:c2 =s.top();
n判断堆栈是否空:s.empty(),如果为空则函数返回true,如果不空则返回false
第一行输入一个t,表示下面将有t组测试数据。接下来的t行的每行输入一个表达式,表达式只考虑英文半角状态输入,无需考虑中文全角输入
对于每一行的表达式,检查括号是否匹配,匹配则输入ok,不匹配则输出error
样例查看模式?
正常显示查看格式
2
(a+b)[4*5+(-6)]
[5*8]/{(a+b)-6
ok
error
4
{1+1}[3+3](5+5)
((({{{}}})))
((({{{}}})))([[]])
((({{{5+5}}})))([[]])(1+1)
ok
ok
ok
ok
#include<iostream>
#include<stack>
#include<vector>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
string s;
cin >> s;
stack<char>st;
bool flag = 0;
for (int i = 0; i < s.size(); i++)
{
if (s[i] == '(' || s[i] == '[' || s[i] == '{')
{
st.push(s[i]);
}
else if (s[i] == ')')
{
if (st.top() != '(')
{
flag = 1;
break;
}
else
{
st.pop();
}
}
else if (s[i] == ']')
{
if (st.top() != '[')
{
flag = 1;
break;
}
else
{
st.pop();
}
}
else if (s[i] == '}')
{
if (st.top() != '{')
{
flag = 1;
break;
}
else
{
st.pop();
}
}
else continue;
}
if (flag || !st.empty())
{
cout << "error" << endl;
}
else cout << "ok" << endl;
}
return 0;
}
计算一个表达式的运算结果
使用C++自带stack堆栈对象来实现
参考课本的算法伪代码P53-54
例如
1. Push (OPTR, '#');表示把字符#压入堆栈OPTR中,转换成c++代码就是OPTR.push('#');
2. Pop(OPND, a); 表示弹出栈OPND的栈顶元素,并把栈顶元素放入变量a中。因此改成c++代码是两个操作:
a = OPND.top(); ? OPND.pop();
3. a = GetTop(OPND)表示获取栈OPND的栈顶元素,转成c++代码就是: a = OPND.top()
第一个输入t,表示有t个实例
第二行起,每行输入一个表达式,每个表达式末尾带#表示结束
输入t行
每行输出一个表达式的计算结果,计算结果用浮点数(含4位小数)的格式表示
用cout控制浮点数输出的小数位数,需要增加一个库文件,并使用fixed和setprecision函数,代码如下:
#include <iostream>
#include<iomanip>
using namespace std;
int main()
{ double temp = 12.34
cout<<fixed<<setprecision(4)<<temp<<endl;
}
输出结果为12.3400
#include<bits/stdc++.h>
using namespace std;
char opset[7]={'+','-','*','/','(',')','#'};
char Prior[7][7]=//列为当前,行为栈顶
{
'>','>','<','<','<','>','>',
'>','>','<','<','<','>','>',
'>','>','>','>','<','>','>',
'>','>','>','>','<','>','>',
'<','<','<','<','<','=',' ',
'>','>','>','>',' ','>','>',
'<','<','<','<','<',' ','='
};
char precede(char aop,char bop)
{
int x,y;
for(int i=0;i<7;i++)
{
if(opset[i]==aop)
{
x=i;
}
if(opset[i]==bop)
{
y=i;
}
}
return Prior[x][y];
}
int In(char Test,char* Testop)
{
for(int i=0;i<7;i++)
{
if(Test==Testop[i])
{
return 1;
}
}
return 0;
}
double Operate(double a,char theta,double b)
{
if(theta=='+')
{
return a+b;
}
else if(theta=='-')
{
return b-a;
}
else if(theta=='*')
{
return a*b;
}
else if(theta=='/')
{
return b/a;
}
//-----a/b stack(b/a)
}
double EvaluateExpression(string exp)
{
stack<double>opnd;//操作数
stack<char>optr;//操作运算符
char tempdata[20];
double data,a,b,r;
char theta,dr[2];
char c;
int i=0;
//先放入#
optr.push('#');
c=exp[0];
strcpy(tempdata,"\0");
//遇到两个#停止
while(c!='#'||optr.top()!='#')
{
if(!In(c,opset))//不是运算符,是数字
{
dr[0]=c;
dr[1]='\0';
strcat(tempdata,dr);
//c为下一个字符
c=exp[++i];
//c是运算符
if(In(c,opset))
{
//转换为数字
data=(double)atof(tempdata);
opnd.push(data);
strcpy(tempdata,"\0");
}
}
else//是数字
{
switch(precede(optr.top(),c))
{
case '<'://栈顶元素优先权低
optr.push(c);
c=exp[++i];
break;
case '=':
optr.pop();
c=exp[++i];
break;
case '>'://栈顶元素优先权低
theta=optr.top();
optr.pop();
a=opnd.top();
opnd.pop();
b=opnd.top();
opnd.pop();
opnd.push(Operate(a,theta,b));
break;
}
}
}
return opnd.top();
}
int main()
{
string exp;
int t;
double result;
cin>>t;
while(t--)
{
cin>>exp;
result=EvaluateExpression(exp);
cout<<fixed<<setprecision(4)<<result<<endl;
}
return 0;
}