C语言怎么把中缀表达式通过栈变成后缀表达式

将中缀表达式转换为后缀表达式是编译器和解释器中的一个经典问题。我们可以通过栈来实现这一过程。以下是使用 C 语言实现的代码。 ### 中缀转后缀的核心思想 1. **操作符优先级**：定义每个操作符的优先级。 2. **栈的使用**： - 使用栈来存储操作符。 - 遇到操作数时直接输出。 - 遇到左括号时压入栈中。 - 遇到右括号时弹出栈中的操作符直到遇到左括号。 - 遇到操作符时，比较其与栈顶操作符的优先级。如果栈顶操作符优先级更高或相等，则弹出栈顶操作符并输出，直到栈顶操作符优先级较低为止。 3. **最终处理**：当整个中缀表达式扫描完毕后，将栈中剩余的操作符依次弹出并输出。 以下是完整的 C 语言代码： ```c #include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> #define MAX_SIZE 100 typedef struct { char data[MAX_SIZE]; int top; } Stack; void init(Stack *s) { s->top = -1; } int isEmpty(Stack *s) { return (s->top == -1); } void push(Stack *s, char value) { if (s->top == MAX_SIZE - 1) { printf("Stack Overflow\n"); exit(1); } s->data[++(s->top)] = value; } char pop(Stack *s) { if (isEmpty(s)) { printf("Stack Underflow\n"); exit(1); } return s->data[(s->top)--]; } int precedence(char op) { if (op == '+' || op == '-') return 1; if (op == '*' || op == '/') return 2; if (op == '^') return 3; return 0; } int isOperator(char ch) { return (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^'); } void infixToPostfix(char *infix, char *postfix) { Stack s; init(&s); int i = 0, j = 0; while (infix[i] != '\0') { if (isspace(infix[i])) { i++; continue; } if (isdigit(infix[i]) || isalpha(infix[i])) { // 如果是操作数，直接复制到后缀表达式 postfix[j++] = infix[i++]; } else if (infix[i] == '(') { // 左括号直接入栈 push(&s, infix[i++]); } else if (infix[i] == ')') { // 右括号则弹出直到遇到左括号 while (!isEmpty(&s) && s.data[s.top] != '(') { postfix[j++] = pop(&s); } if (!isEmpty(&s) && s.data[s.top] == '(') { pop(&s); // 弹出左括号 } i++; } else if (isOperator(infix[i])) { // 操作符处理：比较优先级 while (!isEmpty(&s) && precedence(s.data[s.top]) >= precedence(infix[i])) { postfix[j++] = pop(&s); } push(&s, infix[i++]); } } // 弹出栈中剩余的操作符 while (!isEmpty(&s)) { postfix[j++] = pop(&s); } postfix[j] = '\0'; // 结束字符串 } int main() { char infix[MAX_SIZE], postfix[MAX_SIZE]; printf("请输入中缀表达式: "); fgets(infix, sizeof(infix), stdin); // 去掉输入中的换行符 infix[strcspn(infix, "\n")] = 0; infixToPostfix(infix, postfix); printf("后缀表达式: %s\n", postfix); return 0; } ``` ### 解释 1. **栈的定义**： - 使用结构体 `Stack` 定义了一个栈，包含一个数组 `data` 和一个整型变量 `top` 表示栈顶位置。 2. **初始化函数 `init()`**： - 将栈顶指针初始化为 `-1`，表示栈为空。 3. **判断栈是否为空 `isEmpty()`**： - 如果栈顶指针为 `-1`，则栈为空。 4. **入栈函数 `push()`**： - 将一个字符压入栈中，并更新栈顶指针。 5. **出栈函数 `pop()`**： - 弹出栈顶元素，并返回该值，同时更新栈顶指针。 6. **优先级函数 `precedence()`**： - 定义了每个操作符的优先级，`+` 和 `-` 的优先级最低，`*` 和 `/` 次之，`^` 最高。 7. **判断是否为操作符 `isOperator()`**： - 判断给定字符是否为操作符（如 `+`, `-`, `*`, `/`, `^`）。 8. **核心转换函数 `infixToPostfix()`**： - 遍历中缀表达式的每个字符。 - 如果是数字或字母，则直接复制到后缀表达式。 - 如果是左括号，则压入栈中。 - 如果是右括号，则弹出栈中的操作符直到遇到左括号。 - 如果是操作符，则比较其与栈顶操作符的优先级。如果栈顶操作符优先级更高或相等，则弹出栈顶操作符并输出，直到栈顶操作符优先级较低为止。 9. **主函数 `main()`**： - 用户输入中缀表达式，程序将其转换为后缀表达式并输出。 ### 示例运行 假设用户输入中缀表达式 `3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3`，程序执行过程如下： - 输出的后缀表达式为 `3 4 2 * 1 5 - 2 3 ^ ^ / +`。 ###