中缀表达式转二叉树并后序计算

本篇代码是用C语言实现的一个简易计算器，它主要功能是将用户通过键盘输入的中缀算术表达式转换成一棵二叉表达式树，并通过后序遍历的方式计算表达式的值。整个程序包括以下几个关键部分： 1. **数据结构**: - 定义了两个结构体`s1`和`s2`： - `structs1`用于表示二叉树节点，包含一个字符`data`（存储运算符或操作数），一个浮点数`FIG`（用于存储数字），以及指向下一个节点的指针`next1`和`next2`。 - `structs2`是一个数组`ka`，存储运算符及其对应的优先级，方便后续处理。 2. **函数定义**: - `trans()`函数：用于从输入字符串中提取字符，直到遇到空字符。 - `createBTree(T, chard[])`：这是核心函数，根据输入的字符数组创建二叉树。如果遇到的字符是大写字母，认为是运算符，并在`ka`数组中查找其优先级；如果遇到数字，则视为操作数，继续遍历。同时，该函数处理中缀表达式的优先级解析。 - `search(structs1*e)`：后序遍历二叉树，计算表达式的值。对于二叉树的遍历，这里是后序遍历，即左子树 -> 右子树 -> 当前节点。 3. **主函数**: - 通过`main()`函数接收用户输入的中缀表达式，调用`trans()`函数获取字符数组，然后调用`createBTree()`函数构建二叉树。 - 使用`search()`函数进行后序遍历，计算表达式的结果，并将结果打印出来。循环结构确保可以持续接收用户输入，直到用户停止。 4. **合法性检查**: - 在`createBTree()`函数中，当遇到非运算符时，程序会检查当前是否处于等待运算符的阶段（`flag`变量）。如果是，则认为表达式不合法并设置错误标志。 5. **输入处理**: - 用户输入的是中缀表达式，如`'A'+'B'*C`，通过`trans()`函数逐个字符读取，然后根据字符类型（运算符或数字）构建相应的二叉树节点。 这段代码的核心逻辑是通过C语言实现了中缀表达式到后缀表达式（也称逆波兰表示法）的转换，进而利用后序遍历的特性简化了计算过程。同时，它还包含了错误处理机制，能够检查输入表达式的合法性。这是一项基础但实用的计算机科学技能，对于理解和实践算法设计、编译原理等领域具有重要意义。