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

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

article 2025/3/17 11:25:33

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

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

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

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

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

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

二、后缀表达式的计算

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

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

三、代码实现

以下是完整的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