用栈结构实现表达式求值,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 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);
    } else {
        s->top++;
        s->data[s->top] = x;
    }
}

// 出栈操作
int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Error: stack is empty\n");
        exit(1);
    } else {
        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);
    } else {
        return s->data[s->top];
    }
}

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

// 计算表达式
int evaluate(char *expr) {
    Stack s1, s2;
    initStack(&s1);
    initStack(&s2);

    for (int i = 0; expr[i] != '\0'; i++) {
        if (isdigit(expr[i])) {
            int num = 0;
            while (isdigit(expr[i])) {
                num = num * 10 + (expr[i] - '0');
                i++;
            }
            i--;
            push(&s2, num);
        } else if (isOperator(expr[i])) {
            while (!isEmpty(&s1) && peek(&s1) != '(' && ((expr[i] == '*' || expr[i] == '/') || (expr[i] == '+' || expr[i] == '-') && (peek(&s1) == '+' || peek(&s1) == '-'))) {
                int op1 = pop(&s2);
                int op2 = pop(&s2);
                char op = pop(&s1);
                if (op == '+') {
                    push(&s2, op2 + op1);
                } else if (op == '-') {
                    push(&s2, op2 - op1);
                } else if (op == '*') {
                    push(&s2, op2 * op1);
                } else if (op == '/') {
                    push(&s2, op2 / op1);
                }
            }
            push(&s1, expr[i]);
        } else if (expr[i] == '(') {
            push(&s1, expr[i]);
        } else if (expr[i] == ')') {
            while (!isEmpty(&s1) && peek(&s1) != '(') {
                int op1 = pop(&s2);
                int op2 = pop(&s2);
                char op = pop(&s1);
                if (op == '+') {
                    push(&s2, op2 + op1);
                } else if (op == '-') {
                    push(&s2, op2 - op1);
                } else if (op == '*') {
                    push(&s2, op2 * op1);
                } else if (op == '/') {
                    push(&s2, op2 / op1);
                }
            }
            pop(&s1);
        }
    }

    while (!isEmpty(&s1)) {
        int op1 = pop(&s2);
        int op2 = pop(&s2);
        char op = pop(&s1);
        if (op == '+') {
            push(&s2, op2 + op1);
        } else if (op == '-') {
            push(&s2, op2 - op1);
        } else if (op == '*') {
            push(&s2, op2 * op1);
        } else if (op == '/') {
            push(&s2, op2 / op1);
        }
    }

    return pop(&s2);
}

int main() {
    char expr[MAX_SIZE];
    printf("请输入一个表达式：");
    scanf("%s", expr);
    int result = evaluate(expr);
    printf("%s = %d\n", expr, result);
    return 0;
}

这个实现中，我们使用了两个栈来分别存储操作数和操作符。遍历表达式时，遇到数字就将其入操作数栈，遇到操作符就根据优先级判断是否将栈顶元素出栈计算。最后，将操作数栈中剩余的元素依次出栈计算，得到表达式的结果。