c语言堆栈表达式求值的代码

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

#define MAXSIZE 100 // 定义堆栈最大容量

// 定义堆栈结构体
typedef struct {
int data[MAXSIZE];
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 == MAXSIZE - 1;
}

// 入栈
void push(Stack *s, int x) {
if (isFull(s)) {
printf("Stack is full.\n");
exit(1);
}
s->data[++s->top] = x;
}

// 出栈
int pop(Stack *s) {
if (isEmpty(s)) {
printf("Stack is empty.\n");
exit(1);
}
return s->data[s->top--];
}

// 取栈顶元素
int getTop(Stack *s) {
if (isEmpty(s)) {
printf("Stack is empty.\n");
exit(1);
}
return s->data[s->top];
}

// 操作符优先级比较
int priority(char op) {
switch (op) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '(':
return 0;
default:
printf("Invalid operator.\n");
exit(1);
}
}

// 计算表达式的值
int calc(int a, int b, char op) {
switch (op) {
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
if (b == 0) {
printf("Divide by zero.\n");
exit(1);
}
return a / b;
default:
printf("Invalid operator.\n");
exit(1);
}
}

// 中缀表达式求值
int evaluate(char *exp) {
Stack opnd, optr; // 定义操作数堆栈和操作符堆栈
initStack(&opnd);
initStack(&optr);
push(&optr, '('); // 在操作符堆栈底部压入'('
char *p = exp;
while (*p != '\0') {
if (*p >= '0' && *p <= '9') { // 如果是操作数，直接入操作数堆栈
int num = 0;
while (*p >= '0' && *p <= '9') {
num = num * 10 + *p - '0';
p++;
}
push(&opnd, num);
} else if (*p == '(') { // 如果是左括号，直接入操作符堆栈
push(&optr, '(');
p++;
} else if (*p == '+' || *p == '-' || *p == '*' || *p == '/') { // 如果是操作符
while (priority(getTop(&optr)) >= priority(*p)) { // 循环弹出操作符堆栈中优先级不小于当前操作符的操作符，并将其与操作数堆栈中两个操作数进行计算，将结果入操作数堆栈
char op = pop(&optr);
int b = pop(&opnd);
int a = pop(&opnd);
int res = calc(a, b, op);
push(&opnd, res);
}
push(&optr, *p); // 当前操作符入操作符堆栈
p++;
} else if (*p == ')') { // 如果是右括号
while (getTop(&optr) != '(') { // 循环弹出操作符堆栈中左括号之后的操作符，并将其与操作数堆栈中两个操作数进行计算，将结果入操作数堆栈
char op = pop(&optr);
int b = pop(&opnd);
int a = pop(&opnd);
int res = calc(a, b, op);
push(&opnd, res);
}
pop(&optr); // 弹出左括号
p++;
} else {
printf("Invalid character.\n");
exit(1);
}
}
while (!isEmpty(&optr)) { // 处理操作符堆栈中剩余的操作符
char op = pop(&optr);
int b = pop(&opnd);
int a = pop(&opnd);
int res = calc(a, b, op);
push(&opnd, res);
}
return pop(&opnd); // 返回操作数堆栈中的唯一元素，即表达式的值
}

int main() {
char exp[MAXSIZE];
printf("Please input an infix expression:\n");
scanf("%s", exp);
int res = evaluate(exp);
printf("The result is: %d\n", res);
return 0;
}