C++数据结构实验---栈和队列【多项式计算】

举报
海轰Pro 发表于 2021/08/05 23:39:23 2021/08/05
【摘要】 实验二 栈和队列 1.实验内容与要求 理解栈和队列的逻辑结构及应用场景针对实际问题选择循环队列或链栈的方法，编程实现构造、插入、删除等基本操作掌握栈和队列的存储原理 2.实验环境 硬件环境：计算机软件环境:vc++ 3.实验算法伪代码 计算优先级： char Priority(char ch1,char ch2){ int a; int b; swi...

实验二 栈和队列

1.实验内容与要求

  • 理解栈和队列的逻辑结构及应用场景
  • 针对实际问题选择循环队列或链栈的方法，编程实现构造、插入、删除等基本操作
  • 掌握栈和队列的存储原理

2.实验环境

  • 硬件环境：计算机
  • 软件环境:vc++

3.实验算法伪代码

计算优先级：

char Priority(char ch1,char ch2){
	int a;
	int b;
	switch(ch1){
		case '='  : 	a=0; break;
		case '('  : 	a= 1; break;
		case '+'  : 	a= 3; break;
		case '-'  : 	a= 3; break;
		case '*'  : 	a= 5; break;
		case '/'  : 	a= 5; break;
		case '%'  : 	a= 5; break;
		case '^'  : 	a= 7; break;
		case ')'  : 	a= 8; break;
	}
	switch(ch2){
		case '=' : 	b=0; break;
		case '('  : 	b= 8; break;
		case '+' : 	b= 2; break;
		case '-'  : 	b= 2; break;
		case '*'  : 	b= 4; break;
		case '/'  : 	b= 4; break;
		case '%': b= 4; break;
		case '^' : b= 6; break;
		case ')'  : 	b= 1; break;
	}
	if(a<b)
		return '<';
	else if(a==b)
		return '=';
	else return '>';
}

  
 
    
  
  • 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
    •

根据优先级计算结果:

int Compute(int a,int b,char sign){
	int result;
	switch(sign){
		case '+'  : 	result=a+b; break;
		case '-'  : 	result=a-b; break;
		case '*'  : 	result=a*b; break;
		case '/'  : 	result=a/b; break;
		case '%'  : 	result=a%b; break;
		case '^'  : 	result=a^b; break;
	}
	return result;	
}

  
 
    
  
  • 1
    • 
  
  • 2
    • 
  
  • 3
    • 
  
  • 4
    • 
  
  • 5
    • 
  
  • 6
    • 
  
  • 7
    • 
  
  • 8
    • 
  
  • 9
    • 
  
  • 10
    • 
  
  • 11
    • 
  
  • 12
    • 
  
  • 13
    • 
  
  • 14
    • 
  
  • 15
    • 
  
  • 16
    • 
  
  • 17
    • 
  
  • 18
    •

多项式转化（计算是ASCII实现，为了计算多位数，设次算法）:

while(s[i]!='=')
 { if(s[i]>=48&&s[i]<=57)
	 { //cout<<(s[i]-48); sum=sum*10+(s[i]-48); //cout<<sum; k[j]=sum; //cout<<(k[j]-0); i++;
		// cout<<i; //i++; if(s[i]<48||s[i]>57) j++;
	 }
	 else
	 {
	//	 k[] //s[j]=s[i]; sum=0; k[j]=s[i]; j++; i++;
		//j++;
	 }

 }
 k[j]='=';

  
 
    
  
  • 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
    •

4.实验结果

在这里插入图片描述
5.源代码

  #include<iostream>
#include<string>
using namespace std;
template<typename T>
class Node{
public:
T element;
Node *next; Node(T element){
this->element = element;
next = NULL;
}
};
//..................................................................................栈类
template<typename T>
class Stack{
private:
Node<T> *top;
int size;
public:
 
Stack(){
 
Node<T> *newNode = new Node<T>(0);
top = newNode;
size = 0;
 
}
 
int stackLength(){
return size;
}
 
bool stackEmpty(){
if(0==size)
return true;
else
return false;
}
 
void Push(T e){
Node<T> *newNode = new Node<T>(e);
newNode->next = top->next;
top->next = newNode;
size++;
}
 
T Pop(){
Node<T> *current = top->next;
top->next = current->next;
T f=current->element;
delete current;
size--;
return f;
} T getTop(){
return top->next->element;
}
};
 
char Priority(char ch1,char ch2){
int a;
int b;
switch(ch1){
case '=' : a=0;
break;
case '(' : a= 1;
break;
case '+' : a= 3;
break;
case '-' : a= 3;
break;
case '*' : a= 5;
break;
case '/' : a= 5;
break;
case '%' : a= 5;
break;
case '^' : a= 7;
break;
case ')' : a= 8;
break;
}
switch(ch2){
case '=' : b=0;
break;
case '(' : b= 8;
break;
case '+' : b= 2;
break;
case '-' : b= 2;
break;
case '*' : b= 4;
break;
case '/' : b= 4;
break;
case '%': b= 4;
break;
case '^' : b= 6;
break;
case ')' : b= 1;
break;
}
if(a<b)
return '<';
else if(a==b)
return '=';
else
return '>';
}
 
int Compute(int a,int b,char sign){
int result;
switch(sign){
case '+' : result=a+b;
break;
case '-' : result=a-b;
break;
case '*' : result=a*b;
break;
case '/' : result=a/b;
break;
case '%' : result=a%b;
break;
case '^' : result=a^b;
break;
}
return result; }
 
int main()
{
Stack<int> number;
Stack<char> character;
character.Push('=');
cout<<"输入 例：1+（2*3）+2= {括号必须为英文}"<<endl;
//string k="22";
//k[0]=1;
//k[0]=55;
//cout<<(k[0]-0);
string s;
getline(cin,s);
string k="000000000000000000000000000000000000";
 
int sum=0;
int i=0;
int j=0;
 
while(s[i]!='=')
{
 
if(s[i]>=48&&s[i]<=57)
{
//cout<<(s[i]-48);
sum=sum*10+(s[i]-48);
//cout<<sum;
k[j]=sum;
//cout<<(k[j]-0);
i++;
// cout<<i;
//i++;
if(s[i]<48||s[i]>57)
j++;
}
else
{
// k[]
//s[j]=s[i];
sum=0;
k[j]=s[i];
j++;
i++;
//j++;
}
 
}
k[j]='=';
// cout<<(k[0]-0);
//cout<<k[1];
//cout<<(k[2]-0);
//cout<<k[3]; int kk=0; int ch=k[kk++];
//cout<<ch;
char b;
b=static_cast<char>(ch);
//cout<<(b-0);
while(b!='=' || character.getTop()!='='){
if(ch=='+'||ch=='='||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'){ switch( Priority( character.getTop(), b)){
case'<'://栈顶元素优先级低
character.Push(b);
ch = k[kk++];
b=static_cast<char>(ch);
break;
case'=':
character.Pop();
//character.Push(b);
ch = k[kk++];
b=static_cast<char>(ch);
break;
case'>':
number.Push(Compute(number.Pop(),number.Pop(),character.Pop()));
 
break;
}
 
}
else{
number.Push(ch);
ch =k[kk++];
b=static_cast<char>(ch);
}
}
cout<<"答案是"<<" "<<number.getTop()<<'\n'; return 0;
} 
  
 
    
  
  • 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
    • 
  
  • 143
    • 
  
  • 144
    • 
  
  • 145
    • 
  
  • 146
    • 
  
  • 147
    • 
  
  • 148
    • 
  
  • 149
    • 
  
  • 150
    • 
  
  • 151
    • 
  
  • 152
    • 
  
  • 153
    • 
  
  • 154
    • 
  
  • 155
    • 
  
  • 156
    • 
  
  • 157
    • 
  
  • 158
    • 
  
  • 159
    • 
  
  • 160
    • 
  
  • 161
    • 
  
  • 162
    • 
  
  • 163
    • 
  
  • 164
    • 
  
  • 165
    • 
  
  • 166
    • 
  
  • 167
    • 
  
  • 168
    • 
  
  • 169
    • 
  
  • 170
    • 
  
  • 171
    • 
  
  • 172
    • 
  
  • 173
    • 
  
  • 174
    • 
  
  • 175
    • 
  
  • 176
    • 
  
  • 177
    • 
  
  • 178
    • 
  
  • 179
    • 
  
  • 180
    • 
  
  • 181
    • 
  
  • 182
    • 
  
  • 183
    • 
  
  • 184
    • 
  
  • 185
    • 
  
  • 186
    • 
  
  • 187
    • 
  
  • 188
    • 
  
  • 189
    • 
  
  • 190
    • 
  
  • 191
    • 
  
  • 192
    • 
  
  • 193
    • 
  
  • 194
    • 
  
  • 195
    • 
  
  • 196
    • 
  
  • 197
    • 
  
  • 198
    • 
  
  • 199
    • 
  
  • 200
    • 
  
  • 201
    • 
  
  • 202
    • 
  
  • 203
    • 
  
  • 204
    • 
  
  • 205
    • 
  
  • 206
    • 
  
  • 207
    • 
  
  • 208
    • 
  
  • 209
    • 
  
  • 210
    • 
  
  • 211
    • 
  
  • 212
    • 
  
  • 213
    • 
  
  • 214
    • 
  
  • 215
    • 
  
  • 216
    • 
  
  • 217
    • 
  
  • 218
    • 
  
  • 219
    • 
  
  • 220
    • 
  
  • 221
    • 
  
  • 222
    • 
  
  • 223
    • 
  
  • 224
    • 
  
  • 225
    • 
  
  • 226
    • 
  
  • 227
    • 
  
  • 228
    • 
  
  • 229
    • 
  
  • 230
    • 
  
  • 231
    • 
  
  • 232
    • 
  
  • 233
    • 
  
  • 234
    •

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/109107717

【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
C++ 数据结构
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入