c语言利用栈实现表达式求值

以下是利用栈实现表达式求值的C语言代码：

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

#define MAX_SIZE 100 // 栈的最大容量

typedef struct {
int top; // 栈顶指针
int data[MAX_SIZE]; // 栈的数组
} 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, int x) {
if (isFull(s)) {
printf("Error: stack is full.\n");
exit(1);
}
s->top++;
s->data[s->top] = x;
}

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

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

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

// 计算表达式（左操作数 op 右操作数）
int calculate(int op, int left, int right) {
switch (op) {
case '+':
return left + right;
case '-':
return left - right;
case '*':
return left * right;
case '/':
return left / right;
default:
printf("Error: invalid operator.\n");
exit(1);
}
}

// 表达式求值
int evaluateExpression(char *expression) {
Stack operandStack; // 操作数栈
Stack operatorStack; // 操作符栈
initStack(&operandStack);
initStack(&operatorStack);

int i = 0;
while (expression[i] != '\0') {
if (isdigit(expression[i])) { // 数字，入操作数栈
int num = 0;
while (isdigit(expression[i])) {
num = num * 10 + expression[i] - '0';
i++;
}
push(&operandStack, num);
} else if (isOperator(expression[i])) { // 操作符
while (!isEmpty(&operatorStack) && peek(&operatorStack) != '(' && ((expression[i] == '*' || expression[i] == '/') || (expression[i] == '+' || expression[i] == '-') && (peek(&operatorStack) == '+' || peek(&operatorStack) == '-'))) {
// 操作符栈顶为乘除，当前操作符也为乘除，或者操作符栈顶为加减，当前操作符也为加减，优先级比操作符栈顶高，可以出栈计算
int right = pop(&operandStack);
int left = pop(&operandStack);
int op = pop(&operatorStack);
int result = calculate(op, left, right);
push(&operandStack, result);
}
push(&operatorStack, expression[i]);
i++;
} else if (expression[i] == '(') { // 左括号，入操作符栈
push(&operatorStack, expression[i]);
i++;
} else if (expression[i] == ')') { // 右括号，计算括号内的表达式，结果入操作数栈
while (peek(&operatorStack) != '(') {
int right = pop(&operandStack);
int left = pop(&operandStack);
int op = pop(&operatorStack);
int result = calculate(op, left, right);
push(&operandStack, result);
}
pop(&operatorStack); // 弹出左括号
i++;
} else { // 非法字符
printf("Error: invalid character.\n");
exit(1);
}
}

while (!isEmpty(&operatorStack)) { // 处理剩余的操作符
int right = pop(&operandStack);
int left = pop(&operandStack);
int op = pop(&operatorStack);
int result = calculate(op, left, right);
push(&operandStack, result);
}

return pop(&operandStack); // 最终结果为操作数栈唯一的元素
}

int main() {
char expression[MAX_SIZE];
printf("Enter an infix expression: ");
scanf("%s", expression);
int result = evaluateExpression(expression);
printf("The result is: %d\n", result);
return 0;
}