通过中缀表达式转后缀表达式计算复杂表达式

栈操作与表达式解析：从基础到实践

在计算机科学中，栈是一种常用的数据结构，它遵循后进先出（LIFO）的原则。本文将通过一系列函数的实现，探讨栈在括号匹配、中缀表达式转换为后缀表达式以及后缀表达式求值中的应用。

栈操作函数

为了支持栈的使用，我们定义了以下函数：

  • createStack(int maxSize)：创建一个具有指定最大容量的栈。
  • countStack(Stack* stack)：返回栈中元素的数量。
  • push(Stack* stack, Datatype data)：向栈中压入一个元素。
  • pop(Stack* stack)：从栈中弹出一个元素。
  • peek(Stack* stack)：查看但不移除栈顶元素。
  • destoryStack(Stack* stack)：销毁栈并释放内存。

函数说明：

  1. createStack(int maxSize)

    • 参数: int maxSize - 栈的最大容量。
    • 功能: 创建一个新的栈结构，并分配内存。
    • 返回值: Stack* - 返回新创建的栈的指针。

  2. countStack(Stack* stack)

    • 参数: Stack* stack - 指向栈结构的指针。
    • 功能: 返回栈中当前元素的数量。
    • 返回值: int - 栈中元素的数量。

  3. push(Stack* stack, Datatype data)

    • 参数:
      • Stack* stack - 指向栈结构的指针。
      • Datatype data - 要压入栈的数据。
    • 功能: 将一个元素压入栈中。
    • 注意: 如果栈已满，则不执行压栈操作，并打印“栈满”。

  4. pop(Stack* stack)

    • 参数: Stack* stack - 指向栈结构的指针。
    • 功能: 从栈中弹出一个元素。
    • 注意: 如果栈为空，则不执行弹出操作，并打印“空栈”。

  5. peek(Stack* stack)

    • 参数: Stack* stack - 指向栈结构的指针。
    • 功能: 返回栈顶的元素，但不移除它。
    • 返回值: Datatype - 栈顶的元素。
    • 注意: 如果栈为空，则不返回任何值，并可能引发断言失败。

  6. destoryStack(Stack* stack)

    • 参数: Stack* stack - 指向要销毁的栈结构的指针。
    • 功能: 释放栈占用的内存。
//创建栈
Stack* createStack(int maxSize)
{
	Stack* stack = (Stack*)malloc(sizeof(Stack));
	assert(stack);
	stack->data = (Datatype*)malloc(sizeof(Datatype) * maxSize);
	assert(stack->data);
	stack->top = -1;
	stack->maxSize = maxSize;
	return stack;
}

//获取栈中元素个数
int countStack(Stack* stack)
{
	assert(stack);
	return stack->top+1;
}

//数据入栈
void push(Stack* stack, Datatype data)
{
	assert(stack);
	if (countStack(stack)==stack->maxSize)
	{
		printf("栈满\n");
		return;
	}
	else
	{
		stack->top++;
		stack->data[stack->top] = data;
	}
}

//数据出栈
void pop(Stack* stack)
{
	if (countStack(stack) == 0)
	{
		printf("空栈\n");
		return;
	}
	else
	{
		stack->top--;
	}
}

//获取栈顶元素
Datatype peek(Stack* stack)
{
	assert(stack);
	assert(countStack(stack));
	return stack->data[stack->top];
}

//销毁栈
void destoryStack(Stack* stack)
{
	free(stack->data);
	free(stack);
}

在正式进入表达式求值，强烈建议大家阅读《大话数据结构》中关于该篇章的说明

中缀表达式转换为后缀表达式：transform(char* infix, char* suffix)

中缀表达式转换为后缀表达式是编程中的一个重要概念，它简化了表达式的计算过程。我们通过实现transform函数，利用栈来处理运算符的优先级和括号，将中缀表达式转换为后缀表达式。

  1. transform(char* infix, char* suffix)

    • 参数:
      • char* infix - 指向包含中缀表达式的字符串的指针。
      • char* suffix - 指向用于存储后缀表达式的字符串的指针。
    • 功能: 将中缀表达式转换为后缀表达式。
    • 注意: 如果输入的中缀表达式不正确，可能会打印错误消息。

  2. is_operator(char ch)

    • 参数: char ch - 要检查的字符。
    • 功能: 判断一个字符是否是运算符（+, -, *, /）。
    • 返回值: bool - 如果是运算符返回true，否则返回false。

  3. priority(char ch)

    • 参数: char ch - 要检查的运算符字符。
    • 功能: 返回运算符的优先级。
    • 返回值: int - 运算符的优先级，0表示括号，1表示加或减，2表示乘或除。

后缀表达式求值：calculate(char* suffix)

后缀表达式的计算相对直观，我们通过实现calculate函数，使用栈来存储操作数，并在遇到运算符时执行计算，最终得到表达式的值。

  1. fun(char ch, double num1, double num2)

    • 参数:
      • char ch - 运算符字符。
      • double num1 - 第一个操作数。
      • double num2 - 第二个操作数。
    • 功能: 根据运算符和两个操作数计算结果。
    • 返回值: double - 计算的结果。

  2. calculate(char* suffix)

    • 参数: char* suffix - 指向包含后缀表达式的字符串的指针。
    • 功能: 计算后缀表达式的值。
    • 返回值: double - 表达式计算的结果

函数代码：

//中缀表达式转后缀
//辅助函数：
//1.判断是否为运算符 
bool is_operator(char ch)
{
	return ch == '+' || ch == '-' || ch == '*' || ch == '/';
}
//2.判断优先级,优先级越高，则返回值越大
int priority(char ch)
{
	//如果是，则进行下一步操作
	switch (ch)
	{
	case '+':
	case '-':
		return 1;
	case '*':
	case '/':
		return 2;
	case '(':
	case ')':
		return 0;
	}
}

//转换函数：参数说明：infix数组：键盘获取的中缀表达式，suffix数组：空的数组用来存放转换后的结果并且带出
void transform(char* infix, char* suffix)
{
	//此处需要用两个指针分别遍历两个数组
	char* in = infix;
	char* suf = suffix;
	//创建一个新的栈：栈在此处的作用就是一个规则（输入输出）
	Stack* stack = createStack(100);
	//开始遍历数组
	while (*in != '\0')
	{
		//判断是否是数字：如果是，则存入suffin数组
		if (isdigit(*in))
		{
			while (isdigit(*in)||*in=='.')
			{
				*suf = *in;
				suf++;
				in++;
			};
			//加空格（为了数字之间有间隔）
			*suf = ' ';
			suf++;
		}
		//如果是符号( + - * / )，则判断优先级
		else if (is_operator(*in))
		{
			//判断栈是否为空，为空则直接将该符号入栈
			if (countStack(stack) == 0)
			{
				push(stack, *in);
			}
			//不为空则需要比较优先级：
			else
			{
				//当前字符优先级如果高，则存入
				if (priority(*in) > priority(stack->data[stack->top]))
				{
					stack->data[++stack->top] = *in;
				}
				//如果in低于或者等于stack中的，则出栈，注意不要把括号也给出了
				//为了避免这种情况，我们将括号的优先级置为0
				else
				{
					//什么时候停止出栈：当in的运算符高于stack中的(如果全出完了，则停止)
					while (countStack(stack) != 0 && priority(*in) <= priority(stack->data[stack->top]))
					{
						//将出栈的字符存入suf中
						*suf = stack->data[stack->top];
						suf++;
						*suf = ' ';
						suf++;
						pop(stack);
					}
					//然后将该字符存入
					push(stack, *in);
				}
			}
			in++;
		}
		//如果in的是括号，则单独处理
		//1.如果等于 （ ，则入栈
		else if (*in == '(')
		{
			push(stack, *in);
			in++;
		}
		//2.如果等于 ），则进行出栈，直到匹配到（ 为止
		else if (*in == ')')
		{
			while (countStack(stack) != 0 && stack->data[stack->top] != '(')
			{
				*suf = stack->data[stack->top];
				suf++;
				*suf = ' ';
				suf++;
				pop(stack);
			}
			//删除最后留下的'('
			pop(stack);
			in++;
		}
		else
		{
			printf("error input\n");
			return;
		}
	}
	//最后就将栈中所有操作符都出栈即可
	while (countStack(stack) != 0)
	{
		*suf = stack->data[stack->top];
		suf++;
		*suf = ' ';
		suf++;
		pop(stack);
	}
	//为suf赋为\0
	*suf = '\0';
	destoryStack(stack);
}

//计算辅助函数(将字符转化为运算符，并且计算结果)
double fun(char ch,double num1,double num2)
{
	switch (ch)
	{
	case '+':
		return num1 + num2;
	case '-':
		return num2 - num1;
	case '*':
		return num1 * num2;
	case '/':
		return num2 / num1;
	}
}
//后缀表达式求值
double calculate(char* suffix)
{
	//指针遍历数组
	char* suf = suffix;
	Stack* stack=createStack(100);
	while (*suf != '\0')
	{
		//是数字，则进入，直到将该数字全部取出
		if (isdigit(*suf))
		{
			//将字符转化为数字
			double num = (double)(*suf - '0');
			suf++;
			//下一位如果还是数字或者小数点（说明该数字还没有结束），那么进入循环
			while (isdigit(*suf) || *suf == '.')
			{
				//如果是整数，乘10相加运算
				if (isdigit(*suf))
				{
					num = num * 10 + *suf - '0';
					suf++;
				}
				//如果是小数点，则从下一位开始*0.1相加运算,循环计算，直到得出结果
				else if (*suf == '.')
				{
					//跳过小数点
					suf++;
					//frac在后面小数取出时有进位作用
					float frac = 0.1;
					//将小数点后面的数全部计算
					while (isdigit(*suf))
					{
						//得到小数
						float fl = (*suf - '0') * frac;
						//相加
						num += fl;
						//如果下一位还是小数，则需要/10，例如0.12，先是1，经过一次得到0.1，下一个2变为0.02需要*0.01
						frac /= 10;
						suf++;
					}
				}
			}
			//经过上面的操作，此时一个数字已经被取出,我们放到栈中
			push(stack, num);
		}
		//是运算符(不是空格),则需要出栈两个数字，并且做运算
		else if(is_operator(*suf))
		{
			//出栈两个数
			double num1 = stack->data[stack->top];
			pop(stack);
			double num2 = stack->data[stack->top];
			pop(stack);
			//计算结果,而后存入栈中
			double end = fun(*suf, num1,num2);
			push(stack, end);
			suf++;
		}
		//如果是空格，则++
		else
		{
			suf++;
		}
	}
	//最后遍历完成，将栈中结果出栈
	double end = stack->data[stack->top];
	//销毁栈
	destoryStack(stack);
	//返回计算结果
	return end;
}

测试用例： 9+(3-1)*3+10/2

输出：

结语

栈作为一种基础数据结构，在表达式解析和计算中发挥着重要作用。通过本文的函数实现和讨论，我们可以看到栈如何在实际编程问题中被有效利用。理解栈的工作原理和它在算法设计中的应用，对于任何软件开发者来说都是一个宝贵的技能。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/580121.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

终端安全管理软件哪个好？

终端安全管理软件哪个好？

终端安全管理软件是保障企业信息安全的重要工具。 它们能够有效地防范恶意软件、黑客攻击和其他安全威胁&#xff0c;并提供多方面的终端设备安全保护措施。 终端安全软件的功能和保护机制各不相同&#xff0c;这就需要企业根据自身的需求和情况来进行评估和选择。 下面总结了…
阅读更多...
自动化测试

自动化测试

自动化测试 1、quit() 和 close()的区别2、窗口切换3、截图操作 1、quit() 和 close()的区别 1、quit() 是关闭整个浏览器&#xff1b;而close() 是关闭当前的页面&#xff1b; 2、quit() 操作会清空缓存&#xff1b;close() 不会清空缓存&#xff1b; 2、窗口切换 private …
阅读更多...
Python 语音识别系列-实战学习-语音识别特征提取

Python 语音识别系列-实战学习-语音识别特征提取

Python 语音识别系列-实战学习-语音识别特征提取 前言1.预加重、分帧和加窗2.提取特征3.可视化特征4.总结 前言 语音识别特征提取是语音处理中的一个重要环节&#xff0c;其主要任务是将连续的时域语音信号转换为连续的特征向量&#xff0c;以便于后续的语音识别和语音处理任务…
阅读更多...
【leetcode】快慢指针相关题目总结

【leetcode】快慢指针相关题目总结

141. 环形链表 判断链表是否有环&#xff1a;如果链表中存在环&#xff0c;则在链表上不断前进的指针会一直在环里绕圈子&#xff0c;且不能知道链表是否有环。使用快慢指针&#xff0c;当链表中存在环时&#xff0c;两个指针最终会在环中相遇。 /*** Definition for singly-…
阅读更多...
Java动态代理的实现方式

Java动态代理的实现方式

Java动态代理的实现方式 什么是动态代理&#xff1f; 动态代理是一种编程模式&#xff0c;它允许在运行时创建代理对象&#xff0c;以实现对目标对象的方法进行增强&#xff0c;代理对象同名方法内可以执行原有逻辑的同时嵌入执行其他增强逻辑或者其他对象方法。 动态代理的…
阅读更多...
【软考】设计模式之策略模式

【软考】设计模式之策略模式

目录 1. 说明2. 应用场景3. 结构图4. 构成5. 优缺点5.1 优点5.2 缺点 6. 适用性 1. 说明 1.定义一系列的算法&#xff0c;把它们一个个封装起来&#xff0c;并且使它们可以相互替换。2.此模式使得算法可以独立于使用它们的客户而变化。3.策略模式&#xff08;Strategy Pattern…
阅读更多...
请编写函数fun，其功能是：将s所指字符串中下标为偶数同时ASCII值为奇数的字符删除，s中剩余的字符形成的新串放在t所指的数组中。

请编写函数fun，其功能是：将s所指字符串中下标为偶数同时ASCII值为奇数的字符删除，s中剩余的字符形成的新串放在t所指的数组中。

本文收录于专栏：算法之翼 https://blog.csdn.net/weixin_52908342/category_10943144.html 订阅后本专栏全部文章可见。 本文含有题目的题干、解题思路、解题思路、解题代码、代码解析。本文分别包含C语言、C++、Java、Python四种语言的解法完整代码和详细的解析。 题干 请编…
阅读更多...
TCP协议的可靠性详解

TCP协议的可靠性详解

由于网络部分内容相对于来说比较多&#xff0c;本文只针对TCP协议来进行讲解&#xff0c;后面UDP/Http/Https的讲解有可能会单独出一篇文章。 udp协议相对来来说会比tcp简单不少&#xff0c;同时面试频率tcp也会高上不少。 同时本博客也仅仅只是做出部分讲解&#xff0c…
阅读更多...
代码随想录算法训练营Day11 | 20.有效的括号、1047.删除字符串中的所有相邻重复项、150.逆波兰表达式求值

代码随想录算法训练营Day11 | 20.有效的括号、1047.删除字符串中的所有相邻重复项、150.逆波兰表达式求值

20.有效的括号 题目&#xff1a;给定一个只包括 (&#xff0c;)&#xff0c;{&#xff0c;}&#xff0c;[&#xff0c;] 的字符串 s &#xff0c;判断字符串是否有效。 有效字符串需满足&#xff1a; 左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右…
阅读更多...
B站美化插件，支持自定义，太酷辣~

B站美化插件，支持自定义，太酷辣~

大公司的软件和网站通常具有优雅的默认界面设计。 以国内二次元聚集地B站为例&#xff0c;可以说它的UI设计非常吸引人。与其他视频网站繁复的设计相比&#xff0c;B站的界面设计可以说是遥遥领先 然而&#xff0c;总有些人对默认的用户界面感到不满意&#xff0c;他们渴望尝试…
阅读更多...
数字逻辑电路基础-有限状态机

数字逻辑电路基础-有限状态机

文章目录 一、有限状态机基本结构二、verilog写一个基础有限状态机（moore型状态机）三、完整代码一、有限状态机基本结构 本文主要介绍使用verilog编写有限状态机FSM(finite state machine)，它主要由三部分组成，下一状态逻辑电路，当前状态时序逻辑电路和输出逻辑电路。 有…
阅读更多...
Spring Security认证流程分析

Spring Security认证流程分析

我自己的思路 先分别实现 userdetailsService&#xff0c;userDetails&#xff0c;passwordEncoder三个接口&#xff0c; 然后就是写登录逻辑 本文章用的是继承UsernamePasswordAuthenticationFilter这个接口 因为这个框架默认登录逻辑是在这里面的&#xff0c;里面的核心就是…
阅读更多...
【Vue3+Tres 三维开发】01-HelloWord

【Vue3+Tres 三维开发】01-HelloWord

预览 什么是TRESJS 简单的说，就是基于THREEJS封装的能在vue3中使用的一个组件，可以像使用组件的方式去创建场景和模型。优势就是可以快速创建场景和要素的添加，并且能很明确知道创景中的要素构成和结构。 项目创建 npx create-vite@latest # 选择 vue typescript安装依赖…
阅读更多...
广西民族师范学院领导一行莅临泰迪智能科技开展“访企拓岗”活动

广西民族师范学院领导一行莅临泰迪智能科技开展“访企拓岗”活动

4月25日&#xff0c;广西民族师范学院数理与电子信息工程学院党委副书记、纪委书记主战河&#xff0c;数理与电子信息工程学院副院长陆克盛、专任教师韦吉栋、黎运宇、黄恒秋、王贵富莅临广东泰迪智能科技股份有限公司就深入实施“访企拓岗”、强化校企合作、促进毕业生充分就业…
阅读更多...
搞定Microchip MPU的U-boot源码仿真调试

搞定Microchip MPU的U-boot源码仿真调试

文章目录 准备工作编译at91bootstrap和U-boot源码下载并编译at91bootstrap源码下载并编译u-boot源码 使用Eclipse导入U-boot源码并进行配置cfg配置文件内容仿真调试视频教程 在嵌入式Linux开发中&#xff0c;免不了接触到U-boot&#xff0c;随着U-boot功能越来越强大&#xff0…
阅读更多...
2024年4月26日力扣每日一题（1146）

2024年4月26日力扣每日一题（1146）

2024年4月26日力扣每日一题&#xff08;1146&#xff09; 前言 ​ 这道题在做的时候感觉很简单&#xff0c;题意很容易理解&#xff0c;但直接去做直接干爆内存&#xff0c;参考了一下灵神的代码&#xff0c;豁然开朗&#xff0c;觉得这道题很有意思&#xff0c;便想着写篇博…
阅读更多...
【YOLO改进】换遍IoU损失函数之GIoU Loss（基于MMYOLO）

【YOLO改进】换遍IoU损失函数之GIoU Loss（基于MMYOLO）

GIoU损失函数 论文链接:https://arxiv.org/pdf/1902.09630 GIoU&#xff08;Generalized Intersection over Union&#xff09;损失函数是一种用于改善目标检测模型中边界框回归的方法。它是基于传统的IoU&#xff08;交并比&#xff09;损失的一个改进版本&#xff0c;解决了…
阅读更多...
node.js的安装与配置

node.js的安装与配置

Node.js 是一种基于 JavaScript 编程语言的服务器端平台&#xff0c;它可以让你在浏览器之外运行 JavaScript 代码。以下是 Node.js 的安装步骤&#xff1a; 下载 Node.js&#xff1a; 访问 Node.js官网。根据你的操作系统选择合适的版本下载。 运行安装文件&#xff1a; 在下载…
阅读更多...
计算机视觉——使用OpenCV GrabCut算法从图像中移除背景

计算机视觉——使用OpenCV GrabCut算法从图像中移除背景

GrabCut算法 GrabCut算法是一种用于图像前景提取的技术&#xff0c;由Carsten Rother、Vladimir Kolmogorov和Andrew Blake三位来自英国剑桥微软研究院的研究人员共同开发。该技术的核心目标是在用户进行最少交互操作的情况下&#xff0c;自动从图像中分割出前景对象。 在Gra…
阅读更多...
直流有刷电机入门

直流有刷电机入门

文章目录 123455.25.3 1 2 电刷 材质是 石墨 3 130马达 就几毛钱 几块钱这学的就是减速电机P MAX一定 pf*v 降低速度 扭矩就会大 4 还有空载电流 过大负载 时 有堵转电流 &#xff08;可分析电流 来看电机工作状态&#xff09;RPM 转每分钟 5 5.2 这的线圈 是简化后的转子绕组…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站