写一段c++代码,利用链栈将中缀表达式转换为后缀表达式
时间: 2023-10-09 19:08:13 浏览: 98
利用栈将中缀表达式转换为后缀表达式
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAXSIZE 100 // 定义栈的最大长度
typedef struct Stack { // 定义链栈结构
char data;
struct Stack *next;
} Stack;
Stack *createStack() { // 创建空栈
Stack *s = (Stack *) malloc(sizeof(Stack));
s->next = NULL;
return s;
}
void push(Stack *s, char elem) { // 入栈操作
Stack *node = (Stack *) malloc(sizeof(Stack));
node->data = elem;
node->next = s->next;
s->next = node;
}
char pop(Stack *s) { // 出栈操作
if (s->next == NULL) {
printf("Stack is empty!\n");
return '\0';
}
Stack *temp = s->next;
s->next = temp->next;
char elem = temp->data;
free(temp);
return elem;
}
char getTop(Stack *s) { // 获取栈顶元素
if (s->next == NULL) {
return '\0';
}
return s->next->data;
}
int priority(char op) { // 运算符优先级
switch (op) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '(':
return 0;
default:
return -1;
}
}
void infix2postfix(char *infix, char *postfix) { // 中缀转后缀
Stack *s = createStack();
int i = 0, j = 0, len = strlen(infix);
for (; i < len; i++) {
char ch = infix[i];
if (isdigit(ch) || isalpha(ch)) { // 对于数字和字母直接输出
postfix[j++] = ch;
} else if (ch == '(') { // 左括号直接入栈
push(s, ch);
} else if (ch == ')') { // 右括号出栈直到遇到左括号
while (getTop(s) != '(') {
postfix[j++] = pop(s);
}
pop(s);
} else { // 运算符
while (priority(getTop(s)) >= priority(ch)) {
postfix[j++] = pop(s);
}
push(s, ch);
}
}
while (getTop(s) != '\0') { // 栈中剩余元素出栈
postfix[j++] = pop(s);
}
postfix[j] = '\0';
}
int main() {
char infix[MAXSIZE], postfix[MAXSIZE];
printf("请输入中缀表达式:\n");
scanf("%s", infix);
infix2postfix(infix, postfix);
printf("后缀表达式为:%s\n", postfix);
return 0;
}
阅读全文