C语言实现栈数据结构应用实验报告 - 表达式求值 - 常规

C语言实现栈数据结构应用实验报告 - 表达式求值

实验目的

掌握栈的基本概念和实现方式；
熟练掌握栈的基本操作，如入栈、出栈、判断栈空、判断栈满等；
了解栈的应用，如表达式求值、括号匹配、迷宫求解等。

实验原理

栈是一种先进后出的数据结构，它只允许在栈顶进行插入和删除操作。栈的存储可以使用数组或链表来实现。

在本次实验中，我们将使用数组来实现栈的存储。栈的基本操作包括入栈、出栈、判断栈空、判断栈满等。其中，入栈操作将元素压入栈顶，出栈操作将栈顶元素弹出。判断栈空和判断栈满操作分别检查栈是否为空或是否已满。

栈的应用非常广泛，如表达式求值、括号匹配、迷宫求解等。在本次实验中，我们将实现表达式求值的功能。

实验内容

本次实验的主要内容是实现表达式求值，具体步骤如下：

定义一个栈结构体，包括栈顶指针'top'和存储元素的数组'data'。
实现入栈操作'push'和出栈操作'pop'。在'push'操作中，需要判断栈是否已满；在'pop'操作中，需要判断栈是否为空。
实现判断栈空操作'isEmpty'和判断栈满操作'isFull'。
实现表达式求值函数'eval'，该函数接收一个字符串表达式，将其转换为后缀表达式，并计算出表达式的值。
编写'main'函数，测试表达式求值函数的正确性。

实验步骤

定义栈结构体：

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

typedef struct {
    int top; //栈顶指针
    int data[MAX_SIZE]; //存储元素的数组
} Stack;

实现入栈操作'push'：

void push(Stack *s, int x) {
    if (s->top == MAX_SIZE - 1) {
        printf("栈已满，无法入栈！\n");
        return;
    }
    s->data[++s->top] = x;
}

实现出栈操作'pop'：

int pop(Stack *s) {
    if (s->top == -1) {
        printf("栈已空，无法出栈！\n");
        return -1;
    }
    return s->data[s->top--];
}

实现判断栈空操作'isEmpty'：

int isEmpty(Stack *s) {
    return s->top == -1;
}

实现判断栈满操作'isFull'：

int isFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

实现表达式求值函数'eval'：

int eval(char *exp) {
    Stack s;
    s.top = -1;
    int i, a, b;
    for (i = 0; exp[i] != '\0'; i++) {
        if (isdigit(exp[i])) {
            push(&s, exp[i] - '0');
        } else {
            b = pop(&s);
            a = pop(&s);
            switch (exp[i]) {
                case '+':
                    push(&s, a + b);
                    break;
                case '-':
                    push(&s, a - b);
                    break;
                case '*':
                    push(&s, a * b);
                    break;
                case '/':
                    push(&s, a / b);
                    break;
            }
        }
    }
    return pop(&s);
}

编写'main'函数，测试表达式求值函数的正确性：

int main() {
    char exp[MAX_SIZE];
    printf("请输入表达式：\n");
    scanf("%s", exp);
    int result = eval(exp);
    printf("表达式的值为：%d\n", result);
    return 0;
}

实验结果

输入表达式'12+3*'，输出结果为9，符合预期。

实验总结

本次实验通过实现栈的基本操作和表达式求值功能，掌握了栈的基本概念和实现方式，熟练掌握了栈的基本操作，了解了栈的应用，如表达式求值、括号匹配、迷宫求解等。在编写代码的过程中，需要注意栈的容量限制，并进行相应的判断和处理。在实际应用中，栈也是一种非常重要的数据结构，能够有效地解决许多问题。