用c语言代码实现中缀转后缀
时间: 2024-05-15 08:14:39 浏览: 4
好的,我可以回答这个问题。中缀表达式转后缀表达式需要用到栈的数据结构,以下是使用C语言实现的代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h> // 用于判断是否为数字
#define MAX_SIZE 100 // 定义栈的大小
char opStack[MAX_SIZE]; // 运算符栈
int numStack[MAX_SIZE]; // 数字栈
int opTop = -1; // 运算符栈栈顶指针
int numTop = -1; // 数字栈栈顶指针
int getPriority(char op) // 获取运算符优先级
{
if(op == '*' || op == '/')
return 2;
else if(op == '+' || op == '-')
return 1;
else
return 0;
}
void pushOp(char op) // 将运算符入栈
{
if(opTop == MAX_SIZE-1) // 栈满
{
printf("Error: stack is full!\n");
exit(1);
}
opStack[++opTop] = op;
}
void pushNum(int num) // 将数字入栈
{
if(numTop == MAX_SIZE-1) // 栈满
{
printf("Error: stack is full!\n");
exit(1);
}
numStack[++numTop] = num;
}
char popOp() // 弹出并返回栈顶运算符
{
if(opTop == -1) // 栈空
{
printf("Error: stack is empty!\n");
exit(1);
}
return opStack[opTop--];
}
int popNum() // 弹出并返回栈顶数字
{
if(numTop == -1) // 栈空
{
printf("Error: stack is empty!\n");
exit(1);
}
return numStack[numTop--];
}
void infixToPostfix(char* infix, char* postfix) // 将中缀表达式转换为后缀表达式
{
char* p = infix;
char c, op;
int num, n;
while(*p != '\0')
{
if(isdigit(*p)) // 如果是数字,则将其压入数字栈
{
num = 0;
while(isdigit(*p))
{
num = num*10 + (*p - '0');
p++;
}
pushNum(num);
sprintf(postfix+strlen(postfix), "%d ", num); // 将数字添加到后缀表达式中
}
else if(*p == '(') // 如果是左括号,则将其压入运算符栈
{
pushOp(*p);
p++;
}
else if(*p == ')') // 如果是右括号,则将运算符栈中的运算符弹出并添加到后缀表达式中,直到遇到左括号
{
while((c = popOp()) != '(')
{
sprintf(postfix+strlen(postfix), "%c ", c);
n = popNum();
numStack[numTop+1] = n; // 将数字入栈
numTop++;
}
p++;
}
else if(*p == '+' || *p == '-' || *p == '*' || *p == '/') // 如果是运算符
{
while(opTop > -1 && getPriority(opStack[opTop]) >= getPriority(*p))
{
op = popOp();
sprintf(postfix+strlen(postfix), "%c ", op);
n = popNum();
numStack[numTop+1] = n; // 将数字入栈
numTop++;
}
pushOp(*p);
p++;
}
else
{
p++;
}
}
while(opTop > -1) // 将运算符栈中的运算符依次弹出并添加到后缀表达式中
{
c = popOp();
sprintf(postfix+strlen(postfix), "%c ", c);
n = popNum();
numStack[numTop+1] = n; // 将数字入栈
numTop++;
}
}
int main()
{
char infix[MAX_SIZE];
char postfix[MAX_SIZE] = "";
printf("请输入中缀表达式:");
gets(infix);
infixToPostfix(infix, postfix);
printf("后缀表达式为:%s\n", postfix);
return 0;
}
```
这个程序使用了两个栈:运算符栈和数字栈。首先遍历中缀表达式,如果遇到数字,则将其压入数字栈,并添加到后缀表达式中;如果遇到左括号,则将其压入运算符栈;如果遇到右括号,则将运算符栈中的运算符弹出并添加到后缀表达式中,直到遇到左括号;如果遇到运算符,则将运算符栈中的运算符弹出并添加到后缀表达式中直到运算符栈为空或者栈顶运算符的优先级小于当前运算符的优先级,然后将当前运算符压入运算符栈。最后,将运算符栈中的运算符依次弹出并添加到后缀表达式中。
希望能够帮到你!