C语言用栈实现中缀表达式求值

栈是一种后进先出的数据结构，可以用来实现中缀表达式求值。具体实现思路如下： 1. 定义两个栈，一个用来存储操作数，一个用来存储操作符。 2. 从左到右遍历中缀表达式，遇到操作数则直接入操作数栈，遇到操作符则与操作符栈顶元素比较优先级，如果当前操作符优先级较低，则将操作符栈顶元素弹出并与操作数栈顶的两个元素进行运算，将结果入操作数栈，直到当前操作符优先级大于等于操作符栈顶元素优先级或者操作符栈为空，将当前操作符入操作符栈。 3. 遍历完中缀表达式后，将操作符栈中的所有操作符依次弹出并与操作数栈顶的两个元素进行运算，将结果入操作数栈，直到操作符栈为空。 4. 最终操作数栈中剩下的元素即为中缀表达式的计算结果。 以下是C语言实现中缀表达式求值的代码示例： ```c #include <stdio.h> #include <stdlib.h> #include <ctype.h> #define MAX_SIZE 100 typedef struct { int top; int data[MAX_SIZE]; } Stack; void init(Stack *s) { s->top = -1; } int is_empty(Stack *s) { return s->top == -1; } int is_full(Stack *s) { return s->top == MAX_SIZE - 1; } void push(Stack *s, int x) { if (is_full(s)) { printf("Stack overflow\n"); exit(1); } s->data[++s->top] = x; } int pop(Stack *s) { if (is_empty(s)) { printf("Stack underflow\n"); exit(1); } return s->data[s->top--]; } int peek(Stack *s) { if (is_empty(s)) { printf("Stack underflow\n"); exit(1); } return s->data[s->top]; } int is_operator(char c) { return c == '+' || c == '-' || c == '*' || c == '/'; } int priority(char c) { if (c == '+' || c == '-') { return 1; } else if (c == '*' || c == '/') { return 2; } else { return 0; } } int evaluate(char *expr) { Stack operand_stack, operator_stack; init(&operand_stack); init(&operator_stack); int i = 0; while (expr[i] != '\0') { if (isdigit(expr[i])) { int num = 0; while (isdigit(expr[i])) { num = num * 10 + (expr[i] - '0'); i++; } push(&operand_stack, num); } else if (is_operator(expr[i])) { while (!is_empty(&operator_stack) && priority(peek(&operator_stack)) >= priority(expr[i])) { int op2 = pop(&operand_stack); int op1 = pop(&operand_stack); char op = pop(&operator_stack); int result; switch (op) { case '+': result = op1 + op2; break; case '-': result = op1 - op2; break; case '*': result = op1 * op2; break; case '/': result = op1 / op2; break; } push(&operand_stack, result); } push(&operator_stack, expr[i]); i++; } else { i++; } } while (!is_empty(&operator_stack)) { int op2 = pop(&operand_stack); int op1 = pop(&operand_stack); char op = pop(&operator_stack); int result; switch (op) { case '+': result = op1 + op2; break; case '-': result = op1 - op2; break; case '*': result = op1 * op2; break; case '/': result = op1 / op2; break; } push(&operand_stack, result); } return pop(&operand_stack); } ```