1. 全栈程序员必看首页

中缀表达式转换为后缀表达式（C语言代码+详解）

全栈程序员-用户IM • • 未分类

中缀表达式转换为后缀表达式（C语言代码+详解）中缀表达式转换为后缀表达式1.创建栈2.从左向右顺序获取中缀表达式a.数字直接输出b.运算符情况一：遇到左括号直接入栈，遇到右括号将栈中左括号之后入栈的运算符全部弹栈输出，同时左括号出栈但是不输出。情况二：遇到乘号和除号直接入栈，直到遇到优先级比它更低的运算符，依次弹栈。情况三：遇到加号和减号，如果此时栈空，则直接入栈，否则，将栈中优先级高的运算符依次弹栈（注意：加号和减号属于同一个…

大家好，又见面了，我是你们的朋友全栈君。

中缀表达式转换为后缀表达式（思路）

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]!='
/*中缀转后缀函数*/
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);
}
}

')
	{
		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]=='
/*中缀转后缀函数*/
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);
}
}

')
		{
			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]!='
#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;
}

')
	{
		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]=='
#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;
}

')
		{
			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;
}

运行效果截图如下：
在这里插入图片描述

如何实现将中缀表达式转换成后缀表达式后计算值

(https://blog.csdn.net/qq_42552533/article/details/86562791)

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/148663.html原文链接：https://javaforall.cn

【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛

【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

赞 (0)
全栈程序员-用户IM全栈程序员-用户IM
0 0
blank

相关推荐

  • java interface有多个implement的情况下，@Inject调用实现类的选择

    java interface有多个implement的情况下，@Inject调用实现类的选择

    java interface有多个implement的情况下，@Inject调用实现类的选择javainterface有多个implement的情况下，@Inject调用实现类的选择

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年10月19日
  • bWAPP靶场实战[通俗易懂]

    bWAPP靶场实战[通俗易懂]

    bWAPP靶场实战[通俗易懂]文章目录一、靶场介绍二、靶场搭建2.1安装类型2.2独立安装三、漏洞实战SSRF远程文件包含端口扫描一、靶场介绍  集成了超过100余个网络漏洞，phpweb漏洞靶场，能够调制漏洞难度等级（低->中->高）。二、靶场搭建下载：https://sourceforge.net/projects/bwapp/2.1安装类型搭建类型有两种：(虚拟机版本可测试测漏洞类型更多，比如破壳、心脏滴血)独立安装（部署到apache+php+mysql环境下）虚拟机安装（bee

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年9月16日
  • Matlab 计算均方误差MSE的三种方法

    Matlab 计算均方误差MSE的三种方法

    Matlab 计算均方误差MSE的三种方法Matlab计算均方误差MSE的三种方法数据说明：ytest测试集y，真实的y值，是一维数组；ytest_fit基于测试集x预测的y值，是一维数组；test_error是预测误差。第一种方法直接使用matlab中的mse函数，亲测可用。/*ytest测试集y，真实的y值，是一维数组ytest_fit预测的y值，是一维数组test_error是预测误差*/test_error=ytest-ytest_fit;test_mse=mse(test_er

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年9月30日
  • Myeclipse2017SVN插件安装[通俗易懂]

    Myeclipse2017SVN插件安装[通俗易懂]

    Myeclipse2017SVN插件安装[通俗易懂]Myeclipse2017SVN插件安装链接已改为本人资源链接,自取.如果对你有帮助请给评论一下点个赞,十分感谢!

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年7月21日
  • Unity5.0 状态机新增的entry/exit

    Unity5.0 状态机新增的entry/exit

    Unity5.0 状态机新增的entry/exit

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年3月7日
  • MS17010漏洞利用姿势

    MS17010漏洞利用姿势

    MS17010漏洞利用姿势MSF在msf中常规的17-010打法如下扫描是否存在ms17-010漏洞：nmap-n-p445–scriptsmb-vuln-ms17-010192.168.1.0/24–openMSF常规漏洞利用msf>useexploit/windows/smb/ms17_010_eternalbluemsf>setrhost192.168.1.112目标出网时反向打：msf>setpayloadwindows/x64/met..

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年4月29日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号