用二叉树读取只包含加减乘除的中缀表达式，然后打印出后序表达式，最后用堆栈求解该后序表达式。C语言

在C语言中，处理中缀表达式到后缀表达式的转换通常使用词法分析和递归算法，尤其是通过先序遍历转后序遍历的过程。对于加减乘除的运算，我们可以创建一个二叉树，其中节点代表操作符，并按运算优先级排序。 1. **中缀到后缀表达式（逆波兰式）的转换**： - 创建一个空栈用于存储操作符。 - 遍历输入的中缀表达式，如果遇到数字，直接添加到结果后置表达式中。 - 如果遇到操作符，将其与栈顶的操作符比较优先级： - 若当前操作符优先级高于栈顶，则压入栈； - 否则，将栈顶及之前所有元素依次弹出并添加至后置表达式，直到遇到比当前操作符优先级低或相等的为止，然后将当前操作符压入栈。 - 遇到左括号，压入栈；遇到右括号，直到栈顶的左括号匹配，将这一部分的操作符依次弹出并添加至后置表达式。 2. **后置表达式计算**： - 使用一个堆栈来模拟计算过程： - 遇到数字，压入堆栈； - 遇到操作符，从堆栈弹出两个数，执行相应操作并将结果压回堆栈。 - 当遍历完后置表达式，堆栈中剩下的就是最终的计算结果。 ```c #include <stdio.h> #include <stdlib.h> typedef struct Node { char op; struct Node* left, *right; } Node; Node* createNode(char op) { // ... 实现节点创建函数 } void infixToPostfix(char* infix, char* postfix) { Node* root = parseInfix(infix); // 解析中缀表达式得到根节点 int index = 0; stack_t* stack = createStack(); while (root || !isEmpty(stack)) { if (root && isOperator(root->op)) { push(stack, root); root = root->left; } else { postfix[index++] = root->op; root = pop(stack); } } postfix[index] = '\0'; } double evaluatePostfix(char* postfix) { double num = 0.0; stack_t* stack = createStack(); for (char c : postfix) { if (isdigit(c)) num = num * 10 + (c - '0'); else { double b = pop(stack), a = pop(stack); switch (c) { case '+': push(stack, a + b); break; case '-': push(stack, a - b); break; case '*': push(stack, a * b); break; case '/': push(stack, a / b); break; default: printf("Invalid operator: %c\n", c); return -1; // 错误处理 } } } return pop(stack); } // 省略其他辅助函数和数据结构定义 int main() { char infix[] = "2+3*4-5"; char postfix[100]; infixToPostfix(infix, postfix); double result = evaluatePostfix(postfix); printf("Result: %.2f\n", result); return 0; } ```