c 中缀表达式转后缀表达式
时间: 2023-10-14 17:22:28 浏览: 28
中缀表达式转后缀表达式的步骤如下:
1. 初始化一个栈和一个输出字符串。
2. 从左往右扫描中缀表达式的每个字符。
3. 如果是数字,则直接输出到输出字符串。
4. 如果是左括号,压入栈中。
5. 如果是右括号,则将栈中的元素弹出,输出到输出字符串,直到遇到左括号为止,左括号不输出。
6. 如果是运算符,判断其与栈顶运算符的优先级,如果栈顶运算符优先级大于等于该运算符,则将栈顶运算符弹出,输出到输出字符串,直到栈空或栈顶运算符优先级小于该运算符,然后将该运算符压入栈中。
7. 重复步骤 2-6,直到扫描完整个中缀表达式。
8. 如果栈中还有元素,全部弹出,输出到输出字符串。
下面是 C 语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 定义运算符优先级
int priority(char c) {
switch (c) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '(':
return 0;
default:
return -1;
}
}
// 中缀表达式转后缀表达式
char* infix_to_postfix(char* infix) {
int len = strlen(infix);
char* postfix = (char*)malloc((len + 1) * sizeof(char)); // 分配足够的空间
memset(postfix, 0, (len + 1) * sizeof(char)); // 初始化为空字符串
char stack[len]; // 栈
int top = -1; // 栈顶指针
for (int i = 0; i < len; i++) {
char c = infix[i];
if (c >= '0' && c <= '9') { // 数字
int j = i + 1;
while (infix[j] >= '0' && infix[j] <= '9') j++;
strncat(postfix, infix + i, j - i);
strcat(postfix, " ");
i = j - 1;
}
else if (c == '(') { // 左括号
stack[++top] = c;
}
else if (c == ')') { // 右括号
while (top >= 0 && stack[top] != '(') {
postfix[strlen(postfix) + 1] = '\0';
postfix[strlen(postfix)] = stack[top--];
strcat(postfix, " ");
}
if (top >= 0 && stack[top] == '(') {
top--;
}
}
else if (c == '+' || c == '-' || c == '*' || c == '/') { // 运算符
while (top >= 0 && priority(stack[top]) >= priority(c)) {
postfix[strlen(postfix) + 1] = '\0';
postfix[strlen(postfix)] = stack[top--];
strcat(postfix, " ");
}
stack[++top] = c;
}
}
while (top >= 0) { // 弹出栈中剩余的运算符
postfix[strlen(postfix) + 1] = '\0';
postfix[strlen(postfix)] = stack[top--];
strcat(postfix, " ");
}
return postfix;
}
int main() {
char infix[] = "1+2*3-(4/2+5)*6";
char* postfix = infix_to_postfix(infix);
printf("中缀表达式:%s\n", infix);
printf("后缀表达式:%s\n", postfix);
free(postfix);
return 0;
}
```
输出结果为:
```
中缀表达式:1+2*3-(4/2+5)*6
后缀表达式:123*+42/5+6*-
```