时间:2021-05-20
本文实例为大家分享了C语言实现中缀表达式转后缀表达式的具体代码,供大家参考,具体内容如下
中缀表达式转换为后缀表达式(思路)
1.创建栈
2.从左向右顺序获取中缀表达式
a.数字直接输出
b.运算符
情况一:遇到左括号直接入栈,遇到右括号将栈中左括号之后入栈的运算符全部弹栈输出,同时左括号出栈但是不输出。
情况二:遇到乘号和除号直接入栈,直到遇到优先级比它更低的运算符,依次弹栈。
情况三:遇到加号和减号,如果此时栈空,则直接入栈,否则,将栈中优先级高的运算符依次弹栈(注意:加号和减号属于同一个优先级,所以也依次弹栈)直到栈空或则遇到左括号为止,停止弹栈。(因为左括号要匹配右括号时才弹出)。
情况四:获取完后,将栈中剩余的运算符号依次弹栈输出
例:比如将:2*(9+6/3-5)+4转化为后缀表达式 2 9 6 3 / +5 - * 4 +
转换算法代码如下:
void Change(SqStack *S,Elemtype str[]){ int i=0; Elemtype e; InitStack(S); while(str[i]!='\0') { while(isdigit(str[i])) { printf("%c",str[i++]); if(!isdigit(str[i])) { printf(" "); } } if(str[i]=='+'||str[i]=='-') { if(!StackLength(S)) { PushStack(S,str[i]); } else { do { PopStack(S,&e); if(e=='(') { PushStack(S,e); } else { printf("%c ",e); } }while( StackLength(S) && e != '(' ); PushStack(S,str[i]); } } else if(str[i]==')') { PopStack(S,&e); while(e!='(') { printf("%c ",e); PopStack(S,&e); } } else if(str[i]=='*'||str[i]=='/'||str[i]=='(') { PushStack(S,str[i]); } else if(str[i]=='\0') { break; } else { printf("\n输入格式错误!\n"); return ; } i++; } while(StackLength(S)) { PopStack(S,&e); printf("%c ",e); }}完整代码如下:
#include<stdio.h>#include<stdlib.h>#include<ctype.h> #include<assert.h>#define INITSIZE 20#define INCREMENT 10#define MAXBUFFER 20#define LEN sizeof(Elemtype) typedef char Elemtype;typedef struct{ Elemtype *base; Elemtype *top; int StackSize;}SqStack;void InitStack(SqStack *S){ S->base=(Elemtype*)malloc(LEN*INITSIZE); assert(S->base !=NULL); S->top=S->base; S->StackSize=INITSIZE;} void PushStack(SqStack *S,Elemtype c){ if(S->top - S->base >= S->StackSize) { S->base=(Elemtype*)realloc(S->base,LEN*(S->StackSize+INCREMENT)); assert(S->base !=NULL); S->top =S->base+S->StackSize; S->StackSize+=INCREMENT; } *S->top++ = c;}int StackLength(SqStack *S){ return (S->top - S->base);}int PopStack(SqStack *S,Elemtype *c){ if(!StackLength(S)) { return 0; } *c=*--S->top; return 1;}void Change(SqStack *S,Elemtype str[]){ int i=0; Elemtype e; InitStack(S); while(str[i]!='\0') { while(isdigit(str[i])) { printf("%c",str[i++]); if(!isdigit(str[i])) { printf(" "); } } if(str[i]=='+'||str[i]=='-') { if(!StackLength(S)) { PushStack(S,str[i]); } else { do { PopStack(S,&e); if(e=='(') { PushStack(S,e); } else { printf("%c ",e); } }while( StackLength(S) && e != '(' ); PushStack(S,str[i]); } } else if(str[i]==')') { PopStack(S,&e); while(e!='(') { printf("%c ",e); PopStack(S,&e); } } else if(str[i]=='*'||str[i]=='/'||str[i]=='(') { PushStack(S,str[i]); } else if(str[i]=='\0') { break; } else { printf("\n输入格式错误!\n"); return ; } i++; } while(StackLength(S)) { PopStack(S,&e); printf("%c ",e); }}int main(){ Elemtype str[MAXBUFFER]; SqStack S; gets(str); Change(&S,str); return 0;}运行效果截图如下:
如何实现将中缀表达式转换成后缀表达式后计算值
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
C语言数据结构之中缀树转后缀树的实例对于一个中缀表达式a+b*c*(d-e/f)转换成后缀是这样的形式abc*def/-+后缀表达式是相当有用处的,转换成后缀表
本文实例为大家分享了C语言实现对后缀表达式(逆波兰表达式)的求解代码,供大家参考,具体内容如下逆波兰表达式:逆波兰表达式又叫后缀表达式。它是由相应的语法树的后序
本文实例为大家分享了C++实现中缀表达式转后缀表达式的具体代码,供大家参考,具体内容如下一、思路:和中缀表达式的计算类似,只不过不用计算,把表达式输出即可1.用
本文实例为大家分享了C++实现中缀表达式转后缀表达式的具体代码,供大家参考,具体内容如下题目:现有中缀表达式如:1+(2-3)*4+10/5请用栈的特性编写一个
逆波兰表达式定义:传统的四则运算被称作是中缀表达式,即运算符实在两个运算对象之间的。逆波兰表达式被称作是后缀表达式,表达式实在运算对象的后面。逆波兰表达式:a+