数据结构表达式求值C语言代码

#include <stdio.h>
#include <stdlib.h>

// 定义栈结构体
typedef struct {
int top;
int *data;
} Stack;

// 初始化栈
void initStack(Stack *s, int size) {
s->top = -1;
s->data = (int *)malloc(size * sizeof(int));
}

// 入栈
void push(Stack *s, int x) {
s->top++;
s->data[s->top] = x;
}

// 出栈
int pop(Stack *s) {
int x = s->data[s->top];
s->top--;
return x;
}

// 获取栈顶元素
int peek(Stack *s) {
return s->data[s->top];
}

// 判断栈是否为空
int isEmpty(Stack *s) {
return s->top == -1;
}

// 判断当前字符是否为数字
int isDigit(char c) {
return c >= '0' && c <= '9';
}

// 判断当前字符是否为操作符
int isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}

// 获取操作符的优先级
int getPriority(char c) {
if (c == '*' || c == '/') {
return 2;
} else if (c == '+' || c == '-') {
return 1;
} else {
return 0;
}
}

// 对表达式进行求值
int evaluate(char *expression) {
Stack *numberStack = (Stack *)malloc(sizeof(Stack));
Stack *operatorStack = (Stack *)malloc(sizeof(Stack));
initStack(numberStack, strlen(expression));
initStack(operatorStack, strlen(expression));
int i = 0;
while (expression[i] != '\0') {
if (isDigit(expression[i])) {
int number = 0;
while (isDigit(expression[i])) {
number = number * 10 + (expression[i] - '0');
i++;
}
push(numberStack, number);
} else if (isOperator(expression[i])) {
while (!isEmpty(operatorStack) && getPriority(peek(operatorStack)) >= getPriority(expression[i])) {
int b = pop(numberStack);
int a = pop(numberStack);
char op = pop(operatorStack);
int result;
if (op == '+') {
result = a + b;
} else if (op == '-') {
result = a - b;
} else if (op == '*') {
result = a * b;
} else {
result = a / b;
}
push(numberStack, result);
}
push(operatorStack, expression[i]);
i++;
} else {
i++;
}
}
while (!isEmpty(operatorStack)) {
int b = pop(numberStack);
int a = pop(numberStack);
char op = pop(operatorStack);
int result;
if (op == '+') {
result = a + b;
} else if (op == '-') {
result = a - b;
} else if (op == '*') {
result = a * b;
} else {
result = a / b;
}
push(numberStack, result);
}
int result = pop(numberStack);
free(numberStack);
free(operatorStack);
return result;
}

int main() {
char expression[100];
printf("请输入表达式：");
scanf("%s", expression);
int result = evaluate(expression);
printf("表达式的值为：%d\n", result);
return 0;
}