C++版数据结构：从原表达式到后缀式的转换算法

"从原表达式求得后缀式的规律，数据结构基础知识，C++编程，张宏教授讲解" 在计算机科学中，数据结构是核心概念之一，它涉及到如何有效地组织和管理数据，以便于高效地执行算法。张宏教授在讲解数据结构时，特别提到了从原表达式转换为后缀表达式（也称为逆波兰表示法）的规则，这是在编译原理和算法设计中常见的问题。以下是详细的解释： 1) 运算符栈的设立：在转换过程中，我们需要用一个栈来存储运算符。栈是一种后进先出（LIFO）的数据结构，非常适合处理这种问题。 2) 表达式结束符：“#”被用作表达式的结束标记，预设栈底为“#”。这样可以确保在处理完整个表达式后，栈内不遗留任何运算符。 3) 处理操作数：当遍历到表达式中的操作数时，直接将其添加到后缀表达式中，因为操作数不需要与栈中的运算符进行优先级比较。 4) 优先级判断：对于当前运算符，如果它的优先级高于栈顶运算符，那么将当前运算符压入栈中。这是因为根据运算符的优先级规则，优先级高的运算符会先进行运算。 5) 发送运算符：如果当前运算符的优先级不高于栈顶运算符，或者遇到左括号"("，则连续弹出栈顶运算符并发送给后缀表达式，直到遇到优先级更低的运算符或右括号")"为止。右括号出现时，会弹出栈中所有的运算符，直到遇到对应的左括号，然后将这个右括号也发送给后缀表达式。 数据结构是计算机科学与技术学院课程中的重要内容，它包括逻辑结构和物理结构两方面。逻辑结构关注数据元素之间的关系，如集合、线性结构、树型结构和图结构。物理结构则关注数据在内存中的实际存储方式。 例如，电话号码查询系统可以看作是一种线性结构，每个电话号码及其对应的名字形成一对数据元素，这些元素之间是一对一的关系。在设计算法处理这类数据时，理解数据的结构和关系至关重要，因为这直接影响到算法的效率和程序的可维护性。 数据结构课程的目标是研究如何高效地存储和操作数据，同时考虑数据之间的关系，以及如何设计满足特定需求的算法。这门课程对于计算机科学的学生和开发者来说是非常基础且重要的，因为它为编写高质量、高效率的代码提供了理论基础。