上学的时候没有好好读书,学校留下的实验作业从来就没有做过,每次要交实验报告就去找同学拷贝一份,然后自己做适当修改就提交了。
一学期下来感觉什么也没有,在家里自责之余,写点实验。
对于中缀表达式转为后缀表达式,如果考试
比如
中缀表达式:(8+9*10)-4/2+3
其转化思路:
1、将每个操作符对应的两个操作数用括号括上(((8+(9*10))-(4/2))+3)
2、将操作符移到对应的括号外(((8(910*)+)(42)/)-3)+
3、去掉括号即可 8910*+42/-3+
如果要用数据结构中的栈和队列实现
1、用一个字符串存储表达式
2、扫描字符串。当其为0--9时直接入队列,遇到左括号入栈,操作符级别 #:0用于最后判断,+ -:1,* /:2
3、首先向堆中放一个#,当进入堆的操作符的级别不小于栈顶操作符的优先级,则入栈,否则弹出栈顶元素并进入队列,将下一个操作符压入栈。
4、一直循环直到将所有字符处理完
5、最后将所有元素出队列并打印就可得到后缀表达式
#include<stdio.h>
#define Max 20
//自定义栈
template<class Elem>
struct Stack{
int top;
Elem *p;
int size;
};
template<class Elem>
void Set_Ssize(Stack<Elem> &sta,int n){
sta.size=n;
sta.p=new Elem[sta.size];
sta.top=0;
}
template<class Elem>
void Push(Stack<Elem> &sta,Elem item){
sta.p[sta.top++]=item;
}
template<class Elem>
void Pop(Stack<Elem> &sta,Elem &e){
e=sta.p[--sta.top];
}
template<class Elem>
bool IsEmpty(Stack<Elem> &sta){
return sta.top==0;
}
template<class Elem>
bool IsFull(Stack<Elem> &sta){
return sta.top==sta.size;
}
//自定义队列
template<class Elem>
struct MyQuene{
int front;
int rear;
Elem *p;
int size;
};
template<class Elem>
void Set_Qsize(MyQuene<Elem> &Q,int n){
Q.size=n;
Q.front=0;
Q.rear=0;
Q.p=new Elem[Q.size];
}
template<class Elem>
void AddQuene(MyQuene<Elem> &Q,Elem item){
Q.p[Q.rear++]=item;
if(Q.rear==Q.size)
Q.rear=0;
}
template<class Elem>
void DeleteQuene(MyQuene<Elem> &Q,Elem& e){
e=Q.p[Q.front++];
if(Q.front==Q.size)
Q.front=0;
}
template<class Elem>
Elem GetTop(Stack<Elem> &sta){
return sta.p[sta.top-1];
}
template<class Elem>
bool IsEmpty(MyQuene<Elem> &Q){
return Q.front==Q.rear;
}
template<class Elem>
bool IsFull(MyQuene<Elem> &Q){
int len=Q.front<Q.rear?Q.rear-Q.front:Q.rear-Q.front+Q.size;
return len==Q.size-1;
}
//定义运算符的优先级
int GetPrecedence(char a){
switch(a){
case '#':return 0;
case '+':
case '-':return 1;
case '*':
case '/':return 2;
case '^':return 3;
default:break;
}
}
template<class Elem>
void Middle_Bhind(Stack<Elem> &st,MyQuene<Elem>&Mq,char*A,int n){//中缀表达式转为后缀表达式(自己的实验需求)
Set_Ssize(st,n);
Set_Qsize(Mq,n+1);
char tem;
int i=0;
Push(st,'#');
do{
if((A[i]>='0'&&A[i]<='9')||(A[i]>='A'&&A[i]<='Z')||(A[i]>='a'&&A[i]<='z'))
AddQuene(Mq,A[i]);
else if(A[i]=='(')
Push(st,A[i]);
else if(A[i]==')'){
while(GetTop(st)!='('){
Pop(st,tem);
AddQuene(Mq,tem);
}
Pop(st,tem);
}
else if(GetTop(st)=='(')
Push(st,A[i]);
else{
while(GetPrecedence(A[i])<=GetPrecedence(GetTop(st))){
Pop(st,tem);
AddQuene(Mq,tem);
}
Push(st,A[i]);
}
i++;
}while(A[i]!='\0');
while(GetTop(st)!='#'){
Pop(st,tem);
AddQuene(Mq,tem);
}
while(!IsEmpty(Mq)){
DeleteQuene(Mq,tem);
printf("%c",tem);
}
putchar('\n');
}
void main(){
char str[Max];
Stack<char> st;
MyQuene<char>Mq;
printf("请输入中缀表达式:");
gets(str);
printf("后缀表达式:");
Middle_Bhind(st,Mq,str,Max);
}
分享到:
相关推荐
c++使用堆栈实现中缀表达式转后缀表达式
用堆栈实现中缀表达式转后缀,并计算后缀表达式的结果。
堆栈、队列 实际输入输出情况: 正确的表达式 对负数的处理 表达式括号不匹配 表达式出现非法字符 表达式中操作符位置错误 求余操作符左右出现非整数 其他输入错误 数据结构与算法描述 解决问题的整体思路: 将用户...
6:中缀表达式到前缀和后缀表达式(堆栈、队列和树) Lab7:散列(开放寻址和分离链) Lab8:最短路径(具有邻接矩阵的有向图) 每个实验室的讲师提供的测试数据作为 prog # .dat 文件存储在每个目录中
用C++语言封装了操作数(符)、结点、链表、队列、堆栈等数据结构,能对输入的表达式进行中缀式、后缀式转换,能提示输入语法错误,自动计算给出结果。对数据结构C++语言描述的学习有参考价值。
中缀表达式到后缀表达式 用后缀计算表达式 队列 队列结构 树 二叉树结构 二叉搜索树结构 遍历二叉树 html解析器 图形 普里姆 迪杰斯特拉 力码 3sum 3sum_closest 4sum 添加二进制 添加数字 添加字符串 add_two_...
中缀表达式到后缀表达式 用后缀计算表达式 队列 队列结构 树 二叉树结构 二叉搜索树结构 遍历二叉树 html解析器 图形 普里姆 迪杰斯特拉 力码 3sum 3sum_closest 4sum 添加二进制 添加数字 添加字符串 add_two_...
目的:获得有关堆栈和队列结构的实现及其在解决问题中的应用的知识和技能 选项4 任务1.完成练习并在报告中介绍进度 进行将表达式写成后缀表示法的中缀形式的转换,描述步骤S = a + b-c * k /(d * e-f)中的过程; ...
堆栈、线性表相关函数:链和数组实现队列类、 栈类,并有对应的应用——车站调度以及中缀后缀表达式的分析。
后缀表达式的评估 中缀到前缀 前缀表达式的评估 队列 线性队列 循环队列 双端队列 优先队列 树 二叉树遍历二叉树 二叉搜索树 二叉搜索树中的搜索插入操作 二叉搜索树中的删除操作 图表 广度优先搜索遍历 深度优先...
用堆栈求中缀表达式a+b*c/d+e*f的后缀表达式,求出的后缀表达式为( )。 8.含零个字符的串称为( )串,用(表示。其他串称为( )串。任何串中所含字符的个数称为该串的( )。 9.设有字母序列{Q,D,F,X,A,P,N,B,,Y,...
用堆栈求中缀表达式a+b*c/d+e*f的后缀表达式,求出的后缀表达式为( )。 8.含零个字符的串称为( )串,用(表示。其他串称为( )串。任何串中所含字符的个数称为该串的( )。 9.设有字母序列{Q,D,F,X,A,P,N,B,,Y,...
Shunting Yard算法的快速实现。使用调度场算法使用书面convert表达式到(又称逆...技术细节使用堆栈和队列来实现,以保持与原始算法的距离。 100%的测试覆盖率,因为为什么不这样。 :smiling_face_with_sunglasses:
08_间接赋值成立的三个条件和应用场景 09_指针学习思路应用清晰起来 10_指针强化3和指针强化4思想讲解 11_字符串的基本操作 12_数组中括号与指针关系和数组名常量指针分析 13_字符串一级指针内存模型_传智扫地僧 14_...