算数表达式求值程序设计与实现

"於文卓的算数表达式求值演示1，17061833号学生，2018年11月14日完成" 在这个项目中，於文卓同学设计了一个程序，该程序使用算符优先法来计算不含变量的整数算术表达式。这个方法涉及到了数据结构中的栈这一概念，用于处理四则运算（加、减、乘、除）。以下是该项目的主要知识点： 1. **算符优先法**：这是一种解析和求解算术表达式的方法，依据运算符的优先级进行计算。在给定的程序中，会参考教科书表3.1的算符优先关系，例如乘法和除法优先于加法和减法。 2. **栈（Stack）**：栈是一种线性数据结构，具有后进先出（LIFO）的特性。在这个项目中，使用了两个栈，一个是**运算数栈（Operand Stack）**，用于存储运算中的数值；另一个是**运算符栈（Operator Stack）**，用于存储运算符。 - **运算数栈**：通过`InitStack_OPND`、`GetTop_OPND`、`Push_OPND`和`Pop_OPND`等函数进行初始化、获取栈顶元素、插入元素和删除栈顶元素的操作。 - **运算符栈**：同样有对应的初始化、获取栈顶元素、插入和删除操作，但这里的`Pop_OPTR`返回的是字符类型的运算符，因为运算符通常是字符形式如'+', '-', '*', '/'。 3. **运算操作**：核心函数`EvalueateExpression(char* expression)`接收一个字符串形式的表达式，然后根据算符优先规则进行计算。它会结合运算数栈和运算符栈来处理输入的表达式，处理过程中会模拟教科书中例3-1展示的运算符栈、运算数栈的变化。 4. **测试数据**：项目提供了多个测试用例，涵盖了基本的算术运算，括号的使用以及复杂的嵌套表达式。这些测试用例可以验证程序的正确性和健壮性。 5. **算法流程**： - 读取表达式字符串，逐个字符处理。 - 如果是数字，将其压入运算数栈。 - 如果是运算符，根据当前运算符的优先级与运算符栈顶的运算符比较，如果当前运算符优先级更高或栈为空，将运算符压入运算符栈；否则，从运算数栈弹出两个元素进行运算，并将结果压回运算数栈，同时将当前运算符压入栈。 - 遇到括号时，需要特殊处理，括号内的表达式优先计算，直到匹配的括号结束。 - 当所有字符处理完毕，最后运算符栈中应只剩下一个运算符，这时运算数栈的栈顶元素即为表达式的结果。 6. **错误处理**：在实际实现中，程序还需要考虑输入的合法性，如检查语法错误、除数为零的情况等，并作出相应的错误处理。 这个项目展示了如何使用栈数据结构和算符优先法解决算术表达式求值问题，对于理解和实现编译原理或解析技术中的表达式求值部分有着重要的学习价值。