【学习笔记】中缀表达式转后缀表达式及计算
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