数据结构前缀中缀后缀

前言

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

二，前缀与后缀表达式

三，使用栈实现后缀

四，由中缀到后缀

总结

前言

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

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

如何撰写一个表达式？

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

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

操作符的优先级

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）一样逐个提取单词或数字。

详细解析：

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

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

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

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