用 C语言数据结构写输入一个中缀表达式,表达式中有+、-、*、/四种运算以及(、),表达式中的其他符号为大写的字母。实现一个算法,得到相应的后缀表达式。
时间: 2023-05-30 07:04:39 浏览: 89
以下是 C 语言代码实现:
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h> // 包含 isdigit() 函数
#define MAX_SIZE 100
typedef struct {
char data[MAX_SIZE];
int top;
} Stack;
int is_operator(char c) {
return (c == '+' || c == '-' || c == '*' || c == '/');
}
int priority(char op) {
if (op == '*' || op == '/') {
return 2;
} else if (op == '+' || op == '-') {
return 1;
} else {
return 0;
}
}
void init_stack(Stack *s) {
s->top = -1;
}
int is_empty(Stack *s) {
return (s->top == -1);
}
int is_full(Stack *s) {
return (s->top == MAX_SIZE - 1);
}
void push(Stack *s, char c) {
if (is_full(s)) {
printf("Stack is full.\n");
exit(1);
}
s->data[++(s->top)] = c;
}
char pop(Stack *s) {
if (is_empty(s)) {
printf("Stack is empty.\n");
exit(1);
}
return s->data[(s->top)--];
}
char top(Stack *s) {
if (is_empty(s)) {
printf("Stack is empty.\n");
exit(1);
}
return s->data[s->top];
}
void infix_to_postfix(char *infix, char *postfix) {
Stack s;
init_stack(&s);
int i = 0, j = 0;
while (infix[i] != '\0') {
if (isdigit(infix[i])) { // 如果是数字,直接加入后缀表达式
postfix[j++] = infix[i++];
} else if (is_operator(infix[i])) { // 如果是运算符
while (!is_empty(&s) && priority(infix[i]) <= priority(top(&s))) {
postfix[j++] = pop(&s); // 将栈中优先级高于或等于当前运算符的元素弹出并加入后缀表达式
}
push(&s, infix[i++]); // 将当前运算符入栈
} else if (infix[i] == '(') { // 如果是左括号,直接入栈
push(&s, infix[i++]);
} else if (infix[i] == ')') { // 如果是右括号
while (top(&s) != '(') {
postfix[j++] = pop(&s); // 将栈中左括号之后的元素弹出并加入后缀表达式
}
pop(&s); // 弹出左括号
i++;
} else { // 如果是其他字符,忽略
i++;
}
}
while (!is_empty(&s)) { // 将栈中剩余的元素弹出并加入后缀表达式
postfix[j++] = pop(&s);
}
postfix[j] = '\0'; // 在末尾加上字符串结束符
}
int main() {
char infix[MAX_SIZE], postfix[MAX_SIZE];
printf("Please input an infix expression:\n");
scanf("%s", infix);
infix_to_postfix(infix, postfix);
printf("The postfix expression is:\n%s\n", postfix);
return 0;
}