中缀表达式转后缀c
时间: 2023-10-16 15:10:39 浏览: 43
中缀表达式转后缀表达式的算法可以用栈来实现,步骤如下:
1. 初始化两个栈:操作符栈和结果栈。
2. 从左到右扫描中缀表达式,遇到操作数时,直接将其压入结果栈中。
3. 遇到操作符时,比较其与操作符栈栈顶的优先级:
1. 如果操作符栈为空,或者栈顶操作符为左括号"(",则直接将此操作符入栈。
2. 否则,若优先级比栈顶操作符的优先级高或相等,也将其压入操作符栈中。
3. 否则,将操作符栈中的操作符弹出并压入结果栈中,再次转到第3步和操作符栈中新的栈顶操作符相比较。
4. 遇到括号时:
1. 如果是左括号"(",则直接压入操作符栈。
2. 如果是右括号")",则依次弹出操作符栈中的操作符,并压入结果栈,直到遇到左括号为止,此时将这一对括号丢弃。
5. 重复步骤2至4,直到表达式的最右边。
6. 将操作符栈中剩余的操作符依次弹出并压入结果栈中。
7. 此时,输出结果栈中的元素,即为中缀表达式对应的后缀表达式。
下面是C语言代码实现:
```c
#include <stdio.h>
#include <string.h>
#define MAX_SIZE 100
int is_operator(char op) {
return (op == '+' || op == '-' || op == '*' || op == '/');
}
int get_operator_priority(char op) {
switch (op) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
default:
return 0;
}
}
void infix_to_postfix(char infix[], char postfix[]) {
int i, j;
char op_stack[MAX_SIZE], op;
int top = -1;
int len = strlen(infix);
for (i = 0, j = 0; i < len; i++) {
if (infix[i] == ' ') {
continue;
}
if (isdigit(infix[i])) {
postfix[j++] = infix[i];
while (isdigit(infix[++i])) {
postfix[j++] = infix[i];
}
postfix[j++] = ' ';
i--;
} else if (is_operator(infix[i])) {
while (top >= 0 && get_operator_priority(op_stack[top]) >= get_operator_priority(infix[i])) {
postfix[j++] = op_stack[top--];
postfix[j++] = ' ';
}
op_stack[++top] = infix[i];
} else if (infix[i] == '(') {
op_stack[++top] = infix[i];
} else if (infix[i] == ')') {
while (op_stack[top] != '(') {
postfix[j++] = op_stack[top--];
postfix[j++] = ' ';
}
top--;
}
}
while (top >= 0) {
postfix[j++] = op_stack[top--];
postfix[j++] = ' ';
}
postfix[j - 1] = '\0'; // 去掉最后一个空格
}
int main() {
char infix[MAX_SIZE], postfix[MAX_SIZE];
printf("请输入中缀表达式:\n");
fgets(infix, MAX_SIZE, stdin);
infix_to_postfix(infix, postfix);
printf("对应的后缀表达式为:%s\n", postfix);
return 0;
}
```
注意:上述代码假设中缀表达式中的操作数均为一位数字,如果有多位数字,需要使用循环读取完整数字。