中缀表达式的求职问题,要求:先设计一个主函数,把中缀表达式转换为后缀表达式,再设计一个函数,完成后缀表达试的求值计算,设计一个主函数,进行测试,用数据结构c语言版
时间: 2023-06-01 08:01:46 浏览: 122
以下是中缀表达式转后缀表达式的代码:
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#define MAX_SIZE 100
// 定义栈结构体
typedef struct {
char data[MAX_SIZE];
int top;
} Stack;
// 初始化栈
void initStack(Stack *s) {
s->top = -1;
}
// 判断栈是否为空
int isEmpty(Stack *s) {
return s->top == -1;
}
// 判断栈是否已满
int isFull(Stack *s) {
return s->top == MAX_SIZE - 1;
}
// 入栈
void push(Stack *s, char val) {
if (isFull(s)) {
printf("Stack is full.\n");
exit(0);
}
s->data[++s->top] = val;
}
// 出栈
char pop(Stack *s) {
if (isEmpty(s)) {
printf("Stack is empty.\n");
exit(0);
}
return s->data[s->top--];
}
// 获取栈顶元素
char getTop(Stack *s) {
if (isEmpty(s)) {
printf("Stack is empty.\n");
exit(0);
}
return s->data[s->top];
}
// 获取运算符优先级
int getPriority(char op) {
if (op == '*' || op == '/') {
return 2;
} else if (op == '+' || op == '-') {
return 1;
} else {
return 0;
}
}
// 中缀表达式转后缀表达式
void infixToPostfix(char *infix, char *postfix) {
Stack s;
initStack(&s);
int i = 0, j = 0;
while (infix[i] != '\0') {
if (isdigit(infix[i])) {
postfix[j++] = infix[i++];
while (isdigit(infix[i])) {
postfix[j++] = infix[i++];
}
postfix[j++] = ' ';
} else if (infix[i] == '(') {
push(&s, infix[i]);
i++;
} else if (infix[i] == ')') {
while (getTop(&s) != '(') {
postfix[j++] = pop(&s);
postfix[j++] = ' ';
}
pop(&s);
i++;
} else if (infix[i] == '+' || infix[i] == '-' || infix[i] == '*' || infix[i] == '/') {
while (!isEmpty(&s) && getPriority(getTop(&s)) >= getPriority(infix[i])) {
postfix[j++] = pop(&s);
postfix[j++] = ' ';
}
push(&s, infix[i]);
i++;
} else {
i++;
}
}
while (!isEmpty(&s)) {
postfix[j++] = pop(&s);
postfix[j++] = ' ';
}
postfix[j] = '\0';
}
// 后缀表达式求值
int evalPostfix(char *postfix) {
Stack s;
initStack(&s);
int i = 0;
while (postfix[i] != '\0') {
if (isdigit(postfix[i])) {
int num = 0;
while (isdigit(postfix[i])) {
num = num * 10 + postfix[i] - '0';
i++;
}
push(&s, num);
} else if (postfix[i] == '+' || postfix[i] == '-' || postfix[i] == '*' || postfix[i] == '/') {
int num2 = pop(&s);
int num1 = pop(&s);
switch (postfix[i]) {
case '+':
push(&s, num1 + num2);
break;
case '-':
push(&s, num1 - num2);
break;
case '*':
push(&s, num1 * num2);
break;
case '/':
push(&s, num1 / num2);
break;
}
i++;
} else {
i++;
}
}
return pop(&s);
}
int main() {
char infix[MAX_SIZE];
char postfix[MAX_SIZE];
printf("Please input the infix expression: ");
fgets(infix, MAX_SIZE, stdin);
infix[strlen(infix) - 1] = '\0';
infixToPostfix(infix, postfix);
printf("The postfix expression is: %s\n", postfix);
int result = evalPostfix(postfix);
printf("The result is: %d\n", result);
return 0;
}