数据结构 中缀表达式求值

从键盘输入中缀表达式，建立操作数与运算符堆栈，计算并输出表达式的求值结果。 基本要求：实现 +, -, *, /四个二元运算符以及（）； 操作数范围为0至9。 提高要求：实现+, -, *, /四个二元运算符以及（）； 实现+, -两个一元运算符（即正、负号）； 操作数可为任意整型值（程序假定整数及运算范围不超过int型表示范围）。 若两个整数相除，结果只保留整数商（余数丢弃）；每位同学可选择实现基本要求或者提高要求；程序可不处理表达式语法错误。 《数据结构：中缀表达式求值》 中缀表达式求值是计算机科学中一个经典的问题，它涉及到数据结构中的栈操作。本实验旨在让学生掌握堆栈在表达式求值中的应用，通过实现中缀表达式的计算，理解运算符优先级和括号对表达式的影响。 我们需要定义两个栈：数据栈（stack_Num）用于存储操作数，操作符栈（stack_OP）用于存储运算符。数据栈包含基地址（base）、栈顶指针（top）和栈的大小（stack_size），操作符栈同样包含这些元素，但存储的是字符类型，因为运算符通常用字符表示。 算法设计的核心在于解析输入的中缀表达式。从左到右扫描表达式，遇到数字时将其压入数据栈，遇到运算符时，与操作符栈顶的运算符比较优先级。如果当前运算符优先级更高或等于栈顶运算符，就将当前运算符压入操作符栈；反之，就弹出数据栈上的两个操作数，用栈顶运算符进行计算，结果再压回数据栈。遇到左括号 '(' 时，将其压入操作符栈；遇到右括号 ')' 时，计算括号内的表达式并将结果压回数据栈。 在本实验中，有基本要求和提高要求两种实现。基本要求仅支持 +, -, *, / 四个二元运算符和括号，操作数限于0-9之间。提高要求增加了 +, - 两个一元运算符，操作数可为任意整数，且除法结果只保留整数部分。程序不处理语法错误。 程序的输入/输出设计简单明了，用户直接在键盘上输入中缀表达式，以'='作为结束标志，程序计算完成后输出结果。编程语言采用C语言，利用Visual Studio Code作为开发环境，利用C语言的动态内存管理函数malloc和free，以及输入输出函数scanf和printf。 实验的关键函数包括： 1. `Init` 函数：初始化两个栈。 2. `Push` 函数：向两个栈压入元素。 3. `GetTop` 函数：获取操作符栈的栈顶元素但不删除。 4. `Pop` 函数：从两个栈中弹出元素。 5. `Compare` 函数：比较运算符的优先级。 6. `Calculate` 函数：执行表达式的求值过程。 7. `Result` 函数：执行实际的运算操作。 在测试阶段，应针对基本要求和提高要求分别设计测试实例，确保程序能正确处理各种合法表达式，并处理可能的边界情况，如大整数、负数、一元运算符等。 这个实验通过实现中缀表达式求值，让学生深入理解栈这一数据结构的特性及其在实际问题中的应用，同时锻炼了他们的编程能力和逻辑思维能力。通过实际编码、测试和调试，学生能够更好地掌握数据结构和算法在实际问题中的运用。