数据结构 前缀中缀后缀

目录

前言

一，前缀中缀后缀的基本概念

二，前缀与后缀表达式

三，使用栈实现后缀

四，由中缀到后缀

总结

---

前言

这里学习前缀中缀后缀为我们学习树和图做准备，这个主题主要是对于算术和逻辑表达式求值，这个还可以用于算法，因为这个可以提高效率，节省时间

---

一，前缀中缀后缀的基本概念

如何撰写一个表达式？

这个式我们描述一个表达式的过程，这个中间为一个操作符，这个旁边式操作数

就好比如中间的符号就是操作符，旁边的数字就是操作数

操作符的优先级

1，括号（( )  { }  [ ]）

2，幂运算，如果是2^5^6，这个是先从最右边运算，把5的6次方算出来，然后再计算2的3125次方

3，乘除法，（从左到右）

4，加减法，（从左到右）

中缀表达式：1，先看优先级  2，再看同优先级的操作符之间的冲突  3，再来看结合律

但是中缀表达式就是需要括号来规定有限级顺序，要不然有时候会得不到自己想要的答案，很容易犯优先级错误，而且因为加了括号，计算机程序需要考虑有限级的问题，会使计算机效率下降，所以还有不考虑优先级顺序的，这个就是前缀表达式和后缀表达式

二，前缀与后缀表达式

前缀表达式：prefix                中缀表达式：infix                后缀表达式：profix 

前缀表达式

infix	prefix
2+3	+23
p-q	-pq
a+b*c	+a*bc

前缀表达式相比中缀表达式就更快一点，不需要考虑优先级问题，效率更高，计算机自行会处理这个表达式

后缀表达式 

prefix	proefix
2+3	23+
p-q	pq-
a+b*c	abc*+

前缀后缀的理解

这里可能会有点懵逼，那我们把这个式子拆开去理解

前缀	后缀

我们不难发现，中缀相对我们容易理解一些，但是效率较低，就是可读性高

                         前缀和后缀就是可读性差了，但是计算机的效率高

但是为什么还有前缀后缀呢？我们不是要一个就好了吗？其实后缀的效率相比前缀高

• 后缀表达式：

  • 后缀表达式的计算过程非常直观，从左到右扫描表达式，遇到操作数就压入栈，遇到操作符就从栈中弹出操作数进行计算，然后将结果压入栈。

  • 这种计算方式非常适合计算机实现，因为栈的操作（压栈和弹栈）非常高效，且不需要额外的逻辑来处理操作符优先级。

• 前缀表达式：

  • 前缀表达式的计算需要从右向左扫描，这在实现上不如从左到右扫描直观。

  • 每次遇到操作符时，需要确定其操作数的范围，这可能需要额外的逻辑来处理嵌套结构，增加了计算复杂度。

所以我们在使用的时候一般都是用后缀表达式，不是用前缀表达式

三，使用栈实现后缀

我们以23*54*+9-为例子来写写后缀的程序

思路：

第一代代码实现

#include <iostream>
#include <stack>
#include <string>
/*提供string类型提供length()计算字符串长度提供stoi()函数是把字符串的数字展示出来，其他弄掉
*/
#include <sstream>
#include <cctype>    
/*提供isdigit函数 检查是否为字符*/using namespace std;// 函数用于从字符串中提取操作数
int getOperand(const string& expr, int& index) {string operand;while (index < expr.length() && isdigit(expr[index])) {operand += expr[index++];}return stoi(operand);
}// 函数用于计算后缀表达式的值
int evaluatePostfix(const string& expr) {stack<int>s;int index = 0;while (index < expr.length()) {if (isdigit(expr[index])) {// 如果是操作数，压入栈中s.push(getOperand(expr, index));}else {// 如果是操作符，弹出两个操作数进行计算int operand2 = s.top();s.pop();int operand1 = s.top();s.pop();switch (expr[index]) {case '+': s.push(operand1 + operand2); break;case '-': s.push(operand1 - operand2); break;case '*': s.push(operand1 * operand2); break;case '/': s.push(operand1 / operand2); break;}}index++;}// 栈顶元素即为最终结果return s.top();
}int main() {string postfixExpr = "23*54*+";cout << "后缀表达式的计算结果为: " << evaluatePostfix(postfixExpr) << endl;return 0;
}

我们执行这个代码的时候运行这个23*54*+的结果为77，运行结果是错的，为什么呢，我们通过监视来看看怎么回事

我们会发现这个是把23和54压进去了，然后把23和54进行相加，所以实现错了，这里是需要我们逐个逐个输入到栈里面，而不是一次性输入

string库函数

提供string类型
提供length()计算字符串长度
提供stoi()函数是把字符串的数字展示出来，其他弄掉

（小技巧，这里可以利用s.c来监视这个栈里面的各个值，因为这个是底层容器，这里细讲就涉及的比较多了，等作者学完stl库，然后也会发文章讲述） 

所以目前的问题是解决这个逐个输入的问题

第二代代码

#include <iostream>
#include <stack>
#include <sstream>
#include <string>using namespace std;int evaluatePostfix(const string& expr) {stack<int> s;stringstream ss(expr);  //这个就是为一个类似cin作用的类型string token;while (ss >> token) {if (isdigit(token[0])) {s.push(stoi(token));  // 读取完整的数字}else {int operand2 = s.top(); s.pop();int operand1 = s.top(); s.pop();switch (token[0]) {case '+': s.push(operand1 + operand2); break;case '-': s.push(operand1 - operand2); break;case '*': s.push(operand1 * operand2); break;case '/': s.push(operand1 / operand2); break;}}}return s.top();
}int main() {string postfixExpr = "2 3 * 5 4 * +";  // 需要空格分隔cout << "后缀表达式的计算结果为: " << evaluatePostfix(postfixExpr) << endl;return 0;
}

这里我们就是要输入的时候要注意空格的输入

stringstream ss(expr); 这一行的作用是使用 stringstream 来解析字符串 expr，使其能够像读取输入流（cin）一样逐个提取单词或数字。

详细解析：

1. stringstream 是 C++ 标准库中的一个工具，它允许将字符串作为输入流来处理
2. stringstream ss(expr); 创建一个 stringstream 对象 ss，并用 expr 进行初始化
3. 在 while (ss >> token) 这行代码中，ss >> token 逐个读取 expr 中的单词（用空格分隔），存入 token 变量中

这里就是一个流，这里的>>可以理解为从这个流里面取字符提取出来，更cout里<<用法一样的意思，然后识别的到空格或者换行等就会停止当前识别，然后，在继续识别这流里面的字符串，然后用if-else语句来判断是数字和符号这样就可以判断是否为弹出或者压栈

总结我们利用了一个string类型存储这个后缀的字符串，但是要用空格空出对应的数字与符号，然后放入到流里面，用法stringstream 名字(对应的字符串)，然后利用操作数来进行编写

前缀也就是同样的写法，这里留给读者自己编写

四，由中缀到后缀

这里直接包含括号，直接一步到位，但是我们先谈谈这个思路

以A+B*C-D*E为例子

这个思路主要是优先级问题，遇到优先级比栈里面小的话就直接弹出来

但是我们由括号呢 

这里的代码就先不展示了，后续根据需求写 

---

总结

根据这篇文章我们了解了前缀中缀后缀这些东西，这些东西是可以帮助我们以后再算法里面是追求可读性还是效率作为一个很好的基础，然后我们运用了栈和C++来实现了后缀的实现，这样我们就可以更好掌握stl里面栈的使用了和计算机是如何计算这个后缀表达式的