用c语言实现中缀表达式转后缀表达式
时间: 2023-10-26 14:05:37 浏览: 138
中缀表达式转化为后缀表达式
中缀表达式转后缀表达式可以使用栈来实现,具体步骤如下:
1. 定义一个字符栈用于存储运算符,定义一个字符数组用于存储后缀表达式。
2. 从左到右依次处理中缀表达式的每个元素,如果是数字,直接加到后缀表达式中;如果是运算符,将其与栈顶运算符比较,如果栈顶运算符优先级大于等于该运算符优先级,则将栈顶运算符弹出并加入到后缀表达式中,再将该运算符压入栈中,否则直接将该运算符压入栈中。
3. 处理完中缀表达式后,将栈中剩余的运算符依次弹出并加入到后缀表达式中。
4. 后缀表达式即为最终结果。
下面是用C语言实现中缀表达式转后缀表达式的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 100
int priority(char c) {
switch (c) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '(':
return 0;
default:
return -1;
}
}
void infixToPostfix(char infix[], char postfix[]) {
char stack[MAXSIZE];
int top = -1;
int len = strlen(infix);
int i, j = 0;
for (i = 0; i < len; i++) {
if (infix[i] >= '0' && infix[i] <= '9') {
postfix[j++] = infix[i];
} else if (infix[i] == '(') {
stack[++top] = infix[i];
} else if (infix[i] == ')') {
while (stack[top] != '(') {
postfix[j++] = stack[top--];
}
top--;
} else {
while (top >= 0 && priority(stack[top]) >= priority(infix[i])) {
postfix[j++] = stack[top--];
}
stack[++top] = infix[i];
}
}
while (top >= 0) {
postfix[j++] = stack[top--];
}
postfix[j] = '\0';
}
int main() {
char infix[MAXSIZE], postfix[MAXSIZE];
printf("Please input infix expression: ");
scanf("%s", infix);
infixToPostfix(infix, postfix);
printf("Postfix expression is: %s\n", postfix);
return 0;
}
```
这里我们定义了一个 `priority` 函数用于比较运算符的优先级,数字直接加入到后缀表达式中,左括号直接入栈,右括号则将栈中元素弹出并加入到后缀表达式中直到遇到左括号,运算符则依据其优先级与栈顶元素进行比较,如果栈顶元素优先级大于等于该运算符优先级则将栈顶元素弹出并加入到后缀表达式中,否则将该运算符入栈。最后将栈中剩余的元素全部弹出并加入到后缀表达式中,即为最终结果。
阅读全文