写一段c++代码,利用链栈实现中缀表达式转换为后缀表达式
时间: 2024-04-21 08:17:49 浏览: 104
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 100
typedef struct StackNode {
char data;
struct StackNode *next;
} StackNode, *Stack;
Stack initStack() {
Stack s = (Stack) malloc(sizeof(StackNode));
s->next = NULL;
return s;
}
int isEmpty(Stack s) {
return s->next == NULL;
}
void push(Stack s, char data) {
StackNode *p = (StackNode *) malloc(sizeof(StackNode));
p->data = data;
p->next = s->next;
s->next = p;
}
char pop(Stack s) {
if (isEmpty(s)) {
printf("stack is empty\n");
return '\0';
}
StackNode *p = s->next;
char data = p->data;
s->next = p->next;
free(p);
return data;
}
char top(Stack s) {
if (isEmpty(s)) {
printf("stack is empty\n");
return '\0';
}
return s->next->data;
}
int priority(char c) {
if (c == '+' || c == '-') {
return 1;
} else if (c == '*' || c == '/') {
return 2;
} else {
return 0;
}
}
char *infixToPostfix(char *infix) {
int len = strlen(infix);
char *postfix = (char *) malloc(sizeof(char) * (len + 1));
int i, j = 0;
Stack s = initStack();
for (i = 0; i < len; i++) {
if (infix[i] >= '0' && infix[i] <= '9') {
postfix[j++] = infix[i];
} else if (infix[i] == '(') {
push(s, infix[i]);
} else if (infix[i] == ')') {
while (top(s) != '(') {
postfix[j++] = pop(s);
}
pop(s);
} else {
while (!isEmpty(s) && priority(top(s)) >= priority(infix[i])) {
postfix[j++] = pop(s);
}
push(s, infix[i]);
}
}
while (!isEmpty(s)) {
postfix[j++] = pop(s);
}
postfix[j] = '\0';
return postfix;
}
int main() {
char infix[MAXSIZE];
printf("input infix expression: ");
scanf("%s", infix);
char *postfix = infixToPostfix(infix);
printf("postfix expression: %s\n", postfix);
return 0;
}
阅读全文