C语言实现逆波兰式生成算法及实验报告

"这篇实验报告主要探讨了编译原理中的逆波兰式生成，这是一个将中缀表达式转换为后缀表达式的过程，常用于编译器设计。实验目的是理解和实现这个转换过程，并通过C语言编写相关程序。实验步骤包括构建运算符栈、扫描并处理中缀表达式、比较运算符优先级等。提供的参考程序展示了如何进行这个转换操作。" 在编译原理中，逆波兰式（也称为后缀表达式）是一种没有括号的数学表达式表示方法，它通过运算符位于操作数之后的方式来消除运算符优先级的歧义。本实验的目标是实现一个逆波兰式生成器，将常见的中缀表达式，如 "(a + b) * c" 转换为 "a b + c *" 形式的后缀表达式。 实验步骤详述如下： 1. **建立运算符栈**：首先，我们需要一个数据结构来存储运算符，这里采用栈这一数据结构，栈顶的运算符具有最高的优先级。 2. **读入中缀表达式**：输入的中缀表达式会在其末尾添加一个优先级最低的符号（如 '#'），便于处理表达式的结束。 3. **扫描与处理**：从左到右遍历每个字符。遇到数字时，直接输出数字串；遇到运算符时，与栈顶运算符比较优先级。如果当前运算符优先级更高，则入栈；否则，弹出栈顶运算符，直到找到优先级低于或等于当前运算符的运算符，然后将当前运算符入栈。 4. **持续扫描**：重复以上步骤，直到处理完所有字符，确保所有元素都被正确处理。 5. **输出逆波兰式**：完成扫描后，栈中剩余的运算符依次弹出，形成逆波兰表达式。 在给定的参考程序中，可以看到一些关键的函数定义，如 `boo`, `compare`, `not` 和 `forid`，它们分别可能用于识别运算符、比较优先级和其他辅助功能。程序使用了结构体 `danci` 来存储单词类别和属性值，以及数组 `fout`、`G_table`、`k` 和 `word` 作为运行过程中的临时数据存储。 实验的扩展部分鼓励学生尝试处理更复杂的表达式，例如包含布尔运算符的表达式，这会增加算法的复杂性，因为布尔运算符的优先级规则与算术运算符不同。 逆波兰式生成是编译原理中的一个重要概念，它涉及到解析和转换表达式的关键技术。通过这样的实验，学生能够深入理解编译器如何处理语法和优先级，同时也提供了实际编程经验，巩固理论知识。