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

       在这篇博客中，我们将深入分析一个使用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;
}

感谢分享这篇有关C/C++数据结构的文章，涵盖了栈的基本操作、中缀表达式转后缀表达式、删除堆栈中的元素以及表达式的计算等方面的内容。如果读者想深入学习相关主题，以下是一些额外的资源和知识点，以及网址链接：

1. 堆栈相关资源：

• C++ 标准模板库 (STL) - stack：C++中标准库提供的堆栈容器的文档。
• C++ 标准模板库 (STL) - vector：与堆栈有关的底层数据结构之一。
• GeeksforGeeks - Stack Data Structure：GeeksforGeeks 上关于堆栈数据结构的详细教程和实现。

2. 中缀表达式转后缀表达式：

• Shunting Yard Algorithm：维基百科上关于Shunting Yard算法的介绍。
• 中缀表达式转后缀表达式算法：GeeksforGeeks 上的中缀到后缀的算法和实现。

3. C++ 表达式计算：

• C++ 中的字符串流 (Stringstream)：用于将字符串转换为其他数据类型，对表达式计算很有用。
• C++ 中的 switch 语句：用于处理不同运算符的计算。

4. 其他相关资源：

• C++ Primer (书籍)：Stanley B. Lippman等人编写的 C++ 入门经典。
• LeetCode：在线刷题平台，提供丰富的数据结构和算法问题，适合提高编程能力。

5. 相关知识点的网址链接：

• C++ 中文网：提供了丰富的C++学习资源和实例。
• Stack Overflow：程序员问答社区，可以在这里提问和查找与编程相关的问题。

希望这些资源能够帮助读者更深入地学习和理解C/C++数据结构及相关算法。