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

【学习笔记】中缀表达式转后缀表达式及计算

C++实现中缀表达式转后缀表达式及后缀表达式的计算

在C++中,实现中缀表达式转换为后缀表达式(逆波兰表达式)以及后缀表达式的计算是一个非常经典的问题。它不仅涉及到栈(Stack)数据结构的使用,还涉及到对运算符优先级的处理。本文将详细介绍如何实现这一过程,并提供完整的代码实现。


一、中缀表达式转后缀表达式

中缀表达式(如 9+8*(7-6)-5/4)是我们日常使用的表达式形式,其中运算符位于操作数之间。而后缀表达式(逆波兰表达式)是一种不需要括号来标识优先级的表达式形式,运算符位于操作数之后(如 9 8 7 6 - * + 5 4 / -)。

将中缀表达式转换为后缀表达式的算法基于栈结构,主要步骤如下:

  1. 初始化:创建一个空栈用于存储运算符,创建一个空字符串(或列表)用于存储后缀表达式的结果。
  2. 遍历中缀表达式:从左到右依次处理中缀表达式中的每个字符。
    • 如果是操作数(数字),直接添加到后缀表达式中。
    • 如果是左括号 '(',直接压入栈中。
    • 如果是右括号 ')',则依次弹出栈顶运算符并添加到后缀表达式中,直到遇到左括号 '(',此时丢弃这对括号。
    • 如果是运算符(+-*/):
      • 如果栈为空,或栈顶是左括号 '(',或当前运算符优先级高于栈顶运算符,则将当前运算符压入栈中。
      • 否则,依次弹出栈顶运算符并添加到后缀表达式中,直到栈为空或栈顶运算符优先级低于当前运算符,然后将当前运算符压入栈中。
  3. 处理剩余运算符:遍历结束后,如果栈中仍有运算符,依次弹出并添加到后缀表达式中。

二、后缀表达式的计算

后缀表达式的计算同样基于栈结构,主要步骤如下:

  1. 初始化:创建一个空栈用于存储操作数。
  2. 遍历后缀表达式:从左到右依次处理后缀表达式中的每个字符。
    • 如果是操作数(数字),直接压入栈中。
    • 如果是运算符(+-*/):
      • 弹出栈顶的两个操作数,注意后弹出的操作数是第一个操作数。
      • 根据运算符对两个操作数进行计算,将结果压入栈中。
  3. 最终结果:遍历结束后,栈顶的元素即为最终计算结果。

三、代码实现

以下是完整的C++代码实现,包括中缀表达式转后缀表达式以及后缀表达式的计算。代码中还包含了调试信息的输出,方便理解每一步的操作。

#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <functional>
using namespace std;

template<typename T>
void printVec(const string& msg, const vector<T>& vec)
{
	cout << msg << " | ";
	for (auto &v : vec)
		cout << v << '\t';
	cout << endl;
}

// 中缀表达式转后缀表达式
string MidToRear(const string& mid)
{
	string rear; // 后缀表达式
	vector<char> stk; // 运算符栈

	// 定义优先级比较函数
	function<bool(const char&, const char&)> isPriorOperator = [](const char& A, const char& B)
	{
		if (A == '-' || A == '+')
			return false;
		return B == '-' || B == '+';
	};

	for (const char& ch : mid)
	{
		if (isdigit(ch)) // 如果是数字,直接加入后缀表达式
		{
			rear += ch;
		}
		else if (ch == '(') // 左括号直接入栈
		{
			stk.push_back(ch);
		}
		else if (ch == ')') // 右括号,弹出栈顶元素直到遇到左括号
		{
			while (stk.back() != '(')
			{
				rear += stk.back();
				stk.pop_back();
			}
			stk.pop_back(); // 弹出左括号
		}
		else if (stk.empty() || isPriorOperator(ch, stk.back()) || stk.back() == '(') // 当前运算符优先级高或栈顶是左括号
		{
			stk.push_back(ch);
		}
		else // 当前运算符优先级低,弹出栈顶元素直到优先级合适
		{
			while (!stk.empty() && stk.back() != '(' && !isPriorOperator(ch, stk.back()))
			{
				rear += stk.back();
				stk.pop_back();
			}
			stk.push_back(ch);
		}

		// 输出当前状态
		cout << "current ch: " << ch << "\trearExp: \t" << rear << endl;
		printVec("STACK:", stk);
	}

	// 处理栈中剩余的运算符
	while (!stk.empty())
	{
		rear += stk.back();
		stk.pop_back();
	}

	return rear;
}

// 计算后缀表达式
double CalRear(const string& rear)
{
	vector<double> stk; // 操作数栈

	// 定义计算函数
	auto CalFunc = [](double a, double b, char op) -> double
	{
		if (op == '+')
			return a + b;
		else if (op == '-')
			return a - b;
		else if (op == '/')
			return a / b;
		else if (op == '*')
			return a * b;
		throw std::invalid_argument("error");
	};

	for (auto& ch : rear)
	{
		if (isdigit(ch)) // 如果是数字,直接入栈
		{
			stk.push_back(ch - '0');
		}
		else // 如果是运算符,弹出两个操作数进行计算
		{
			double b = stk.back();
			stk.pop_back();
			double a = stk.back();
			stk.pop_back();
			double cal = CalFunc(a, b, ch);
			stk.push_back(cal);
		}

		// 输出当前状态
		cout << "current ch: " << ch << "\trearExp: \t" << rear << endl;
		printVec("STACK:", stk);
	}

	return stk.back(); // 栈顶元素即为最终结果
}

int main()
{
	// 示例输入
	string mid;
	cout << "请输入中缀表达式(仅支持数字和 + - * / ( )): ";
	cin >> mid;

	// 中缀转后缀
	auto rear = MidToRear(mid);
	cout << "后缀表达式: " << rear << endl << endl;

	// 计算后缀表达式
	cout << "计算结果: " << CalRear(rear) << endl;

	return 0;
}

四、程序输出

以下是程序的运行输出示例,你可以根据实际输入填写输出结果。

输入示例:

9+8*(7-6)-5/4

输出示例:

 9+8*(7-6)-5/4
current ch: 9   rearExp:        9
STACK: |
current ch: +   rearExp:        9
STACK: | +
current ch: 8   rearExp:        98
STACK: | +
current ch: *   rearExp:        98
STACK: | +      *
current ch: (   rearExp:        98
STACK: | +      *       (
current ch: 7   rearExp:        987
STACK: | +      *       (
current ch: -   rearExp:        987
STACK: | +      *       (       -
current ch: 6   rearExp:        9876
STACK: | +      *       (       -
current ch: )   rearExp:        9876-
STACK: | +      *
current ch: -   rearExp:        9876-*+
STACK: | -
current ch: 5   rearExp:        9876-*+5
STACK: | -
current ch: /   rearExp:        9876-*+5
STACK: | -      /
current ch: 4   rearExp:        9876-*+54
STACK: | -      /
9876-*+54/-

current ch: 9   rearExp:        9876-*+54/-
STACK: | 9
current ch: 8   rearExp:        9876-*+54/-
STACK: | 9      8
current ch: 7   rearExp:        9876-*+54/-
STACK: | 9      8       7
current ch: 6   rearExp:        9876-*+54/-
STACK: | 9      8       7       6
current ch: -   rearExp:        9876-*+54/-
STACK: | 9      8       1
current ch: *   rearExp:        9876-*+54/-
STACK: | 9      8
current ch: +   rearExp:        9876-*+54/-
STACK: | 17
current ch: 5   rearExp:        9876-*+54/-
STACK: | 17     5
current ch: 4   rearExp:        9876-*+54/-
STACK: | 17     5       4
current ch: /   rearExp:        9876-*+54/-
STACK: | 17     1.25
current ch: -   rearExp:        9876-*+54/-
STACK: | 15.75

Cal ans:15.75


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

相关文章:

  • 编程助手学Python--Deepseek对Langchain的调用OpenAI的GPT-3.5模型起名字与格式化输出
  • Git基础篇 - Linux(CentOS)源码安装Git实例
  • 四元数 实部 虚部顺序,不同仿真器
  • 鸿蒙next 多行文字加图片后缀实现方案
  • Win10 下搭建免费的 FTP 服务器 FileZilla
  • Ubuntu 配置 github 代理
  • Ktor库使用HTTP编写了一个下载程序
  • LinuX---搜索查找类命令
  • PHP语法基础
  • Nginx + Docker 反向代理多个项目
  • Flutter 学习之旅 之 flutter 实现简单自定义的倒计时 CountdownTimer 功能/监听倒计时开始/结束/计时中的事件
  • px4中的UAVCAN_V1特点与仲裁原理
  • 数据分析项目:基于LSTM的微博评论情感分析
  • ctf-web: xss 任意位置插入情况绕过 DOMPurify -- tpctf layout
  • XEngine Kit
  • SCSS详解
  • fastapi+angular实现Tcp在线聊天室功能
  • 如何快速定位导致服务器卡顿的进程
  • 云原生持续交付:自动化部署的智能引擎
  • 前端高阶面试题·每日一题