当前位置： 首页 > article >正文

HJ50-四则运算：栈的运用、中缀表达式转后缀表达式并计算结果

article 2024/11/17 1:50:20

文章目录

  • 题目
  • 一、分析
      • 1.1表达式预处理
      • 1.2中缀表达式转后缀
      • 1.3 后缀表达式计算结果
  • 二、答案

题目

在这里插入图片描述

一、分析

通过利用栈将中缀表达式转换为后缀表达式，在根据后缀表达式计算运算结果。由于包含负数操作数的情况，并且操作数位数不固定为1，因此，需要对输入的表达式进行预处理，将操作数和操作符进行分离，并且将大括号和中括号统一为小括号。

1.1表达式预处理

/// <summary>
/// 预处理表达式
/// </summary>
/// <param name="data">中缀表达式</param>
/// <returns>表达式</returns>
std::vector<std::string>  pretreat(const std::string& data)
{
		std::string value = data;
		//->处理括号
		for (int i = 0; i < value.size(); i++)
		{
				if (value[i] == '[' || value[i] == '{') value[i] = '(';
				if (value[i] == ']' || value[i] == '}') value[i] = ')';
		}
		//->处理负数,并将运算符与运算数拆分开
		value = '(' + value + ')';	
		int index = -1;
		std::vector<std::string> content;
		for (int i = 0; i < value.size(); i++)
		{
				//->负数操作数的情况
				if (value[i] == '-' && (i - 1) >= 0 && value[i - 1] == '(' && (i + 1) < value.size() && value[i + 1] >= '0' && value[i + 1] <= '9')
				{
						index = i;
						continue;
				}
				//->非负数操作数
				else if (value[i] >= '0' && value[i] <= '9' && index == -1)
				{
						index = i;
				}
				if ((value[i] < '0' || value[i] > '9') && index != -1)
				{
						content.push_back(value.substr(index, i - index));
						index = -1;
				}
				if ((value[i] < '0' || value[i] > '9') && index == -1)
				{
						content.push_back(value.substr(i, 1));
				}
		}
		return content;
}

1.2中缀表达式转后缀

1.2.1 对于中缀表达式A+B*(C-D)-E/F转后后缀表达式时，栈中数据变化情况如下。

1.2.2 栈内和栈外操作符的优先级如下。

std::map<std::string, int> isp = { {"#",0}, {"(",1},  {"*",5},  {"/",5},  {"+",3},  {"-",3},  {")",6} };//->栈内操作符的优先级
std::map<std::string, int> icp = { {"#",0}, {"(",6},  {"*",4},  {"/",4},  {"+",2},  {"-",2},  {")",1} };//->栈外操作符的优先级

1.2.3 代码逻辑伪代码如下，可根据此变化设计代码逻辑。

步扫描项项类型动作栈变化输出
0“#”进栈#
1A操作数#A
2+操作符isp[“#”] < icp[“+”],进栈#+A
3B操作数#+AB
4*操作符isp[“+”] < icp[“*”],进栈#+*AB
5(操作符isp[“*”] < icp[“(”],进栈#+*(AB
6C操作数#+*(ABC
7-操作符isp[“(”] < icp[“-”],进栈#+*(-ABC
8D操作数#+*(-ABCD
9)操作符isp[“-”] >icp[“)”],退栈#+*(ABCD-
”(“ == “)”,退栈#+*ABCD-
10-操作符isp[“*”] > icp[“-”],退栈#+ABCD-*
isp[“+”] > icp[“-”],退栈#ABCD-*+
isp[“#”] < icp[“-”],进栈#-ABCD-*+
11E操作数#-ABCD-*+E
12/操作符isp[“-”] < icp[“/”],进栈#-/ABCD-*+E
13F操作数#-/ABCD-*+EF
14#操作符isp[“/”] > icp[“#”],退栈#-ABCD-*+EF/
操作符isp[“-”] > icp[“#”],退栈#ABCD-*+EF/-
结束
/// <summary>
/// 判断是否是操作数
/// </summary>
/// <param name="value"></param>
/// <returns></returns>
bool isDigit(std::string& value)
{
		if (value.empty())
				return false;
		return value.back() >= '0' && value.back() <= '9';
}

/// <summary>
/// 将中缀表达式转换为后缀表达式
/// </summary>
/// <param name="data">中缀表达式</param>
/// <returns>后缀表达式</returns>
std::vector<std::string> postfix(std::vector<std::string>& content)
{
		//->定义栈内操作符和栈外操作符的优先级
		std::map<std::string, int> isp = { {"#",0}, {"(",1},  {"*",5},  {"/",5},  {"+",3},  {"-",3},  {")",6} };//->栈内操作符的优先级
		std::map<std::string, int> icp = { {"#",0}, {"(",6},  {"*",4},  {"/",4},  {"+",2},  {"-",2},  {")",1} };//->栈外操作符的优先级
		content.push_back("#");

		int index = 0;
		std::vector<std::string> expression;
		std::string item1 = "#", item2, item3;
		std::stack<std::string> stack;
		stack.push(item1);
		item1 = content[index];
		index++;

		while (!stack.empty() && item1 != "#")
		{
				if (isDigit(item1))
				{
						expression.push_back(item1);
						item1 = content[index];
						index++;
				}
				else
				{
						item2 = stack.top();
						if (isp[item2] < icp[item1])
						{
								stack.push(item1);
								item1 = content[index];
								index++;
						}
						else if (isp[item2] > icp[item1])
						{
								expression.push_back(stack.top());
								item3 = stack.top();
								stack.pop();
						}
						else
						{
								std::string item = stack.top();
								stack.pop();
								if (item == "(")
								{
										item1 = content[index];
										index++;
								}
						}
				}
		}
		return expression;
}

1.3 后缀表达式计算结果

1.3.1 计算后缀表达式ABCD-*+EF/-栈中元素变化情况，逻辑如下。

步扫描项项类型动作栈中内容
1栈置空空
2A操作数进栈A
3B操作数进栈AB
4C操作数进栈ABC
5D操作数进栈ABCD
6-操作符D、C退栈，计算C-D，结果R1进栈ABR1
7*操作符R1、B退栈，计算B*R1，结果R2进栈BR2
8+操作符R2、B退栈，计算A+R2，结果R3进栈R3
9E操作数进栈R3E
10F操作数进栈R3EF
11/操作符F、E退栈，计算E/F，结果R4进栈R3R4
12-操作符R4、R3退栈。计算R3-R4，结果R5进栈R5
/// <summary>
/// 根据后缀表达式计算结果
/// </summary>
/// <param name="expression"></param>
/// <returns></returns>
float calculator(std::vector<std::string>& expression)
{
		std::stack<float> values;
		for (int i = 0; i < expression.size(); i++)
		{
				std::string value = expression[i];
				if (isDigit(value))
				{
						values.push(std::atoi(value.c_str()));
				}
				else
				{
						float value1 = values.top(); values.pop();
						float value2 = values.top(); values.pop();
						switch (value[0])
						{
						case '+': values.push(value2 + value1); break;
						case '-':  values.push(value2 - value1); break;
						case '*': values.push(value2 * value1); break;
						case '/': values.push(value2 / value1); break;
						default:break;
						}
				}
		}
		return values.top();
}

二、答案

#include  <iostream>
#include <stack>
#include <string>
#include <vector>
#include <map>

/// <summary>
/// 判断是否是操作数
/// </summary>
/// <param name="value"></param>
/// <returns></returns>
bool isDigit(std::string& value)
{
		if (value.empty())
				return false;
		return value.back() >= '0' && value.back() <= '9';
}

/// <summary>
/// 将中缀表达式转换为后缀表达式
/// </summary>
/// <param name="data">中缀表达式</param>
/// <returns>后缀表达式</returns>
std::vector<std::string> postfix(std::vector<std::string>& content)
{
		//->定义栈内操作符和栈外操作符的优先级
		std::map<std::string, int> isp = { {"#",0}, {"(",1},  {"*",5},  {"/",5},  {"+",3},  {"-",3},  {")",6} };//->栈内操作符的优先级
		std::map<std::string, int> icp = { {"#",0}, {"(",6},  {"*",4},  {"/",4},  {"+",2},  {"-",2},  {")",1} };//->栈外操作符的优先级
		content.push_back("#");

		int index = 0;
		std::vector<std::string> expression;
		std::string item1 = "#", item2, item3;
		std::stack<std::string> stack;
		stack.push(item1);
		item1 = content[index];
		index++;

		while (!stack.empty() && item1 != "#")
		{
				if (isDigit(item1))
				{
						expression.push_back(item1);
						item1 = content[index];
						index++;
				}
				else
				{
						item2 = stack.top();
						if (isp[item2] < icp[item1])
						{
								stack.push(item1);
								item1 = content[index];
								index++;
						}
						else if (isp[item2] > icp[item1])
						{
								expression.push_back(stack.top());
								item3 = stack.top();
								stack.pop();
						}
						else
						{
								std::string item = stack.top();
								stack.pop();
								if (item == "(")
								{
										item1 = content[index];
										index++;
								}
						}
				}
		}
		return expression;
}

/// <summary>
/// 预处理表达式
/// </summary>
/// <param name="data">中缀表达式</param>
/// <returns>表达式</returns>
std::vector<std::string>  pretreat(const std::string& data)
{
		std::string value = data;
		//->处理括号
		for (int i = 0; i < value.size(); i++)
		{
				if (value[i] == '[' || value[i] == '{') value[i] = '(';
				if (value[i] == ']' || value[i] == '}') value[i] = ')';
		}
		//->处理负数,并将运算符与运算数拆分开
		value = '(' + value + ')';	
		int index = -1;
		std::vector<std::string> content;
		for (int i = 0; i < value.size(); i++)
		{
				//->负数操作数的情况
				if (value[i] == '-' && (i - 1) >= 0 && value[i - 1] == '(' && (i + 1) < value.size() && value[i + 1] >= '0' && value[i + 1] <= '9')
				{
						index = i;
						continue;
				}
				//->非负数操作数
				else if (value[i] >= '0' && value[i] <= '9' && index == -1)
				{
						index = i;
				}
				if ((value[i] < '0' || value[i] > '9') && index != -1)
				{
						content.push_back(value.substr(index, i - index));
						index = -1;
				}
				if ((value[i] < '0' || value[i] > '9') && index == -1)
				{
						content.push_back(value.substr(i, 1));
				}
		}
		return content;
}

/// <summary>
/// 根据后缀表达式计算结果
/// </summary>
/// <param name="expression"></param>
/// <returns></returns>
float calculator(std::vector<std::string>& expression)
{
		std::stack<float> values;
		for (int i = 0; i < expression.size(); i++)
		{
				std::string value = expression[i];
				if (isDigit(value))
				{
						values.push(std::atoi(value.c_str()));
				}
				else
				{
						float value1 = values.top(); values.pop();
						float value2 = values.top(); values.pop();
						switch (value[0])
						{
						case '+': values.push(value2 + value1); break;
						case '-':  values.push(value2 - value1); break;
						case '*': values.push(value2 * value1); break;
						case '/': values.push(value2 / value1); break;
						default:break;
						}
				}
		}
		return values.top();
}

int main()
{
		std::string data;
		std::cin >> data;
		std::vector<std::string> content = pretreat(data);
		std::vector<std::string> expression = postfix(content);
		std::cout << calculator(expression);
		return 0;
}

http://www.kler.cn/a/323769.html

相关文章：

  • CC6学习记录
  • Java中的集合类与线程安全的讨论
  • 让空间计算触手可及，VR手套何以点石成金？
  • 4. Spring Cloud Ribbon 实现“负载均衡”的详细配置说明
  • C语言编程练习：验证哥德巴赫猜想 进制转换 rand函数
  • 酒水分销积分商城小程序开发方案php+uniapp
  • C++(9.26)
  • FastReport时间格式化（含判空）
  • Python办公自动化之Word
  • 探索未来：MultiOn，AI的下一个革命
  • 示例说明：elasticsearch实战应用
  • 等保托管怎么样，流程是什么样的？
  • 弹性盒模型关键几个点：
  • 【SQL】总结Select语句中用来连接字符串的方法
  • 万字长文详解FreeRTOS软件定时器
  • 机器学习：opencv--特征检测
  • 静态链接和动态链接的Golang二进制文件
  • 音视频入门基础：FLV专题（4）——使用flvAnalyser工具分析FLV文件
  • SQLI—LABS刷题 | SQL总结
  • QT:常用类与组件
  • Humans or LLMs as the Judge? A Study on Judgement Bias
  • Redis6.0.9配置redis集群
  • 银河麒麟高级服务器操作系统V10外接硬盘挂载指南
  • 关于el-card的height设置100%后, el-card内容超出高度后,内容被隐藏这件事
  • Tkinter制作登录界面以及登陆后页面切换--用户数据从数据库获取并进行合法性校验（二）
  • 【WPF】多屏幕展示