石 家 庄 铁 道 大 学
实 验 报 告
课程名称： 信2305-3 任课教师： 刘 丹 实验日期： 2024.12.11
班 级： 信2305-3 姓 名： 徐戌 学 号： 20234316
实验项目名称：实验二
一、 实验目的
1.掌握栈的定义及实现
2.掌握利用栈求解算术表达式。
3.掌握队列的定义及相关算法的实现
二、 实验内容
三、 设计文档
四、 源程序
7-2 栈实现表达式求值
include
include
include
using namespace std;
const int N=100010;
string split(string s){
string ss;
for(int i=0;i<s.size();i++){
if(s[i]==32) continue;
ss+=char(s[i]);
}
return ss;
}
bool ck1(string s){
int cnt=0;
for(int i=0;i<s.size();i++){
if(s[i]'(') cnt++;
else if(s[i]')') cnt--;
}
return cnt==0;
}
bool ck2(string s){
for(int i=0;i<s.size();i++){
if(s[i]'+'||s[i]'-'||s[i]'*'||s[i]'/'){
if(i0||is.size()-1||i&&(s[i-1]'+'||s[i-1]'-'||s[i-1]'*'||s[i-1]'/')){
return 0;
}
}
}
return 1;
}
int pri(char ch){return ch'*'||ch'/'?2:1;}
char ch[N];
int cnt;
string cg(string s){
string ss;
for(int i=0;i<s.size();i++){
if(s[i]>='0'&&s[i]<='9'){
ss+=char(s[i]);
}else{
if(s[i]'('){
ch[cnt++]='(';
}else if(s[i]')'){
while(ch[cnt-1]!='('){
ss+=ch[--cnt];
}
cnt--;
}else{
char c=char(s[i]);
if(cnt>0&&pri(c)<=pri(ch[cnt-1])){
while(cnt>0&&ch[cnt-1]!='('&&pri(c)<=pri(ch[cnt-1])){
ss+=ch[--cnt];
}
}
ch[cnt++]=c;
}
}
}
while(cnt>0){
ss+=ch[--cnt];
}
return ss;
}
int op(int x,int y,char ch){
if(ch'+') return x+y;
else if(ch'-') return x-y;
else if(ch=='') return xy;
else return x/y;
}
int a[N],ct;
int op(string s){
for(int i=0;i<s.size();i++){
if(s[i]>='0'&&s[i]<='9'){
a[ct++]=s[i]-48;
}
else{
int x=a[ct-2],y=a[ct-1];
ct-=2;
a[ct++]=op(x,y,char(s[i]));
}
}
return a[0];
}
int main(){
string s;
getline(cin,s);
s=split(s);
if(!ck1(s)){
cout<<"ERROR:缺少括号";
return 0;
}
if(!ck2(s)){
cout<<"ERROR:表达式缺操作数";
return 0;
}
string ss=cg(s);
cout<<ss<<endl;
cout<<op(ss);
return 0;
}
7-2 队列应用(蓝桥杯)
include
include
include
using namespace std;
int main() {
int M;
cin >> M; // 读取操作次数
queue
for (int i = 0; i < M; ++i) {
string op, name, type;
cin >> op; // 读取操作类型
if (op == "IN") {
cin >> name >> type; // 读取用户名字和队列类型
if (type == "V") {
vipQueue.push(name); // 如果是VIP队列，入队
} else if (type == "N") {
normalQueue.push(name); // 如果是普通队列，入队
}
} else if (op == "OUT") {
cin >> type; // 读取队列类型
if (type == "V" && !vipQueue.empty()) {
vipQueue.pop(); // 如果是VIP队列，出队
} else if (type == "N" && !normalQueue.empty()) {
normalQueue.pop(); // 如果是普通队列，出队
}
}
}
// 输出VIP队列
while (!vipQueue.empty()) {
cout << vipQueue.front() << endl;
vipQueue.pop();
}
// 输出普通队列
while (!normalQueue.empty()) {
cout << normalQueue.front() << endl;
normalQueue.pop();
}
return 0;
}
五、 个人体会
优先级问题：可以使用一个优先级表来存储每个操作符的优先级。在处理表达式时，根据当前操作符和栈顶操作符的优先级来决定是将当前操作符压入栈中还是将栈顶操作符弹出并执行计算。括号的处理：当遇到左括号时，将其压入栈中。当遇到右括号时，不断弹出栈顶操作符并执行计算，直到遇到左括号为止。然后将左括号从栈中弹出。
实验感想：通过这次实现表达式求值的过程，我深刻体会到了栈在处理复杂数据结构和算法中的强大能力。栈的后进先出特性使得它非常适合处理涉及优先级和顺序的问题，如表达式求值。在这个过程中，我也学到了如何更好地进行错误处理和边界条件的检查，这对于编写健壮的代码非常重要。
此外，通过实际编码，我对算法和数据结构的理解也更加深入了。这种实践经验不仅提升了我的编程技能，也增强了我解决问题的能力。未来，我会继续探索更多的算法和数据结构，不断提升自己的技术水平。