c语言利用栈实现表达式求值线性结构

以下是利用栈实现表达式求值的C语言代码： ``` #include <stdio.h> #include <stdlib.h> #define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int top; } Stack; void initStack(Stack *s) { s->top = -1; } int isStackEmpty(Stack *s) { return s->top == -1; } int isStackFull(Stack *s) { return s->top == MAX_SIZE - 1; } void push(Stack *s, int x) { if (isStackFull(s)) { printf("Stack overflow!\n"); exit(1); } s->data[++s->top] = x; } int pop(Stack *s) { if (isStackEmpty(s)) { printf("Stack underflow!\n"); exit(1); } return s->data[s->top--]; } int getTop(Stack *s) { if (isStackEmpty(s)) { printf("Stack is empty!\n"); exit(1); } return s->data[s->top]; } 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 1; } else if (c == '*' || c == '/') { return 2; } else { return 0; } } int calculate(int a, int b, char op) { if (op == '+') { return a + b; } else if (op == '-') { return a - b; } else if (op == '*') { return a * b; } else if (op == '/') { return a / b; } else { return 0; } } int evaluateExpression(char *exp) { Stack numStack, opStack; initStack(&numStack); initStack(&opStack); int i = 0; while (exp[i] != '\0') { if (isDigit(exp[i])) { int num = 0; while (isDigit(exp[i])) { num = num * 10 + exp[i] - '0'; i++; } push(&numStack, num); } else if (isOperator(exp[i])) { while (!isStackEmpty(&opStack) && getPriority(exp[i]) <= getPriority(getTop(&opStack))) { int b = pop(&numStack); int a = pop(&numStack); char op = pop(&opStack); int result = calculate(a, b, op); push(&numStack, result); } push(&opStack, exp[i]); i++; } else { i++; } } while (!isStackEmpty(&opStack)) { int b = pop(&numStack); int a = pop(&numStack); char op = pop(&opStack); int result = calculate(a, b, op); push(&numStack, result); } return pop(&numStack); } int main() { char exp[MAX_SIZE]; printf("Enter an infix expression: "); fgets(exp, MAX_SIZE, stdin); int result = evaluateExpression(exp); printf("Result: %d\n", result); return 0; } ``` 该程序首先定义了一个栈结构体，包含一个整型数组和一个栈顶指针。然后定义了一些栈操作函数，如初始化栈、判断栈是否为空或已满、入栈、出栈和获取栈顶元素等。接着定义了一些辅助函数，如判断字符是否为数字或运算符、获取运算符优先级和计算两个操作数的结果等。 evaluateExpression函数是该程序的核心函数，用于将中缀表达式转换为后缀表达式并求值。该函数使用两个栈，一个用于存储操作数，一个用于存储运算符。遍历中缀表达式的每个字符，如果是数字则将其压入操作数栈中，如果是运算符则将其与运算符栈顶的运算符比较优先级，如果优先级高则将其压入运算符栈中，否则从运算符栈中弹出运算符和两个操作数，计算它们的结果并将结果压入操作数栈中，直到当前运算符的优先级大于运算符栈顶的运算符或运算符栈为空。最后将剩余的运算符和操作数依次弹出并计算它们的结果，最终得到表达式的值。 该程序使用fgets函数从标准输入读取中缀表达式，然后调用evaluateExpression函数求值并输出结果。