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

C/C++数据结构之中缀表达式转换为后缀表达式，删除堆栈元素

news 2025/7/28 15:27:58

在这篇博客中，我们将深入分析一个使用C++编写的栈和表达式计算程序。该程序不仅实现了基本的栈操作，还提供了中缀表达式转后缀表达式和删除堆栈中的元素等实用功能。通过逐一讲解每个函数的功能，我们将更全面地理解这个程序的实现。

资源获取：

官方途径：点击博主头像，主页下载资源，需花费积分！
个人途径：公众号：每日推荐系列，回复【表达式转换】免费获取！

核心数据结构

1. 栈的实现

struct Node { ... };
struct Stack { ... };

Node结构：表示栈的元素，包含一个整数类型的数据和指向下一个结点的指针。
Stack结构：自定义栈，包含栈顶指针和栈的大小。提供了基本的入栈、出栈、获取栈顶元素、判断栈是否为空等操作。

详细功能解析

1. 中缀表达式转后缀表达式（主要功能函数 ①）

string zhuanhuan(const string& infix) {   //方法都大差不差string postfix;Stack operatorStack;for (char ch : infix) {if (isdigit(ch)) {postfix += ch;}else if (ch == '(') {operatorStack.Push(ch);}else if (ch == ')') {while (......略......) {......略......}if (......略......) {......略......}}else {while (!operatorStack.IsEmpty() && operatorStack.Top() != '(' &&......略......}operatorStack.Push(ch);}}while (!operatorStack.IsEmpty()) {......略......}return postfix;
}

主要函数过程是遍历中缀表达式，使用栈辅助转换。数字直接输出，左括号入栈，右括号弹出栈元素直到遇到左括号，运算符按照优先级处理。

效果图如下：

2. 删除堆栈中的元素（主要功能函数 ②）

    void Delete(int value) {  //删除指定元素......略......while (!IsEmpty()) {int topValue = Top();Pop();if (topValue == value) {......略......}else {......略......}}if (!found) {cerr << "未找到要删除的元素" << endl;}else {......略......}while (!reversedValues.empty()) {......略......cout << endl;}}};

删除堆栈中的元素，使用临时栈将不需要删除的元素暂存，输出删除的元素，最终恢复原始栈的值。

效果图如下：

3. 表达式计算（非主要功能）


double EvaluatePostfix(const std::string& postfix) {   std::stack<double> operandStack;for (char ch : postfix) {   if (std::isdigit(ch) || (ch == '.')) {......略......}else if (ch == ' ') {#####略######}else {    //俩俩的算，运算之后再次push进去######略#######switch (ch) {case '+':operandStack.push(a + b);break;case '-':operandStack.push(a - b);break;case '*':operandStack.push(a * b);break;case '/':operandStack.push(a / b);break;}}}return operandStack.top();
}

遍历后缀表达式，使用栈存储操作数，遇到运算符则弹出栈顶两个元素进行计算，将结果压入栈中。

4.其他函数：

4.1. `Stack Pushand()`

Stack Pushand() {Stack stack;// ... 省略部分代码 ...return stack;
}

用户输入堆栈数据个数，并逐个输入数字，构建堆栈。
输出堆栈中的值，并返回构建好的堆栈。

4.2. `void Printf()` 和 `void Printf_2()`

void Printf() {// ... 省略部分代码 ...
}void Printf_2() {// ... 省略部分代码 ...
}

Printf：打印主菜单，显示功能选项。
Printf_2：打印功能结束提示。

4.3. `void choice_1()` 和 `void choice_2()`

void choice_1() {// ... 省略部分代码 ...
}void choice_2() {// ... 省略部分代码 ...
}

choice_1：执行中缀表达式转后缀表达式的操作，输出后缀表达式和计算结果。
choice_2：执行删除堆栈中元素的操作，输出删除后的堆栈。

主函数如下：

int main() {int choice;do {Printf();cout << "请输入选择：";cin >> choice;switch (choice) {case 1:choice_1();break;case 2:choice_2();break;case 0:break;default:cout << "无效的选择，请重新输入" << endl;Printf_2();}} while (choice != 0);return 1111111111111111111;
}