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

一、实验目的

通过本次实验，学生应该能够掌握以下知识：

理解栈的基本概念和基本操作；
掌握用栈实现表达式求值的方法；
熟悉栈在计算机编程中的应用。

二、实验环境

操作系统：Windows 10；
编程语言：C。

三、实验内容

实现栈的基本操作；
用栈实现表达式求值。

四、实验步骤

1. 栈的基本操作实现

栈是一种特殊的线性表，具有后进先出的特点。栈的基本操作包括入栈、出栈、获取栈顶元素和判断栈是否为空。下面是栈的基本操作实现的代码：

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef struct {
    int *base;    // 栈底指针
    int *top;     // 栈顶指针
    int stacksize;  // 当前已分配的存储空间
} SqStack;

// 初始化栈
void InitStack(SqStack *S)
{
    S->base = (int *)malloc(STACK_INIT_SIZE * sizeof(int));
    if (!S->base) {
        exit(0);
    }
    S->top = S->base;
    S->stacksize = STACK_INIT_SIZE;
}

// 入栈操作
void Push(SqStack *S, int e)
{
    if (S->top - S->base >= S->stacksize) {
        S->base = (int *)realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(int));
        if (!S->base) {
            exit(0);
        }
        S->top = S->base + S->stacksize;
        S->stacksize += STACKINCREMENT;
    }
    *(S->top++) = e;
}

// 出栈操作
int Pop(SqStack *S, int *e)
{
    if (S->top == S->base) {
        return 0;
    }
    *e = *(--S->top);
    return 1;
}

// 获取栈顶元素
int GetTop(SqStack *S, int *e)
{
    if (S->top == S->base) {
        return 0;
    }
    *e = *(S->top - 1);
    return 1;
}

// 判断栈是否为空
int StackEmpty(SqStack *S)
{
    if (S->top == S->base) {
        return 1;
    }
    return 0;
}

2. 表达式求值实现

表达式求值是栈的一种常见应用。本次实验中，我们将用栈实现表达式求值。表达式求值的步骤如下：

定义两个栈，一个用于存储操作数，另一个用于存储运算符；
从左到右扫描表达式；
如果遇到操作数，将其压入操作数栈；
如果遇到运算符，将其压入运算符栈；
如果遇到右括号，弹出运算符栈中的运算符，弹出操作数栈中的两个操作数，进行运算，并将结果压入操作数栈；
最后，操作数栈中剩下的操作数就是表达式的值。

下面是用栈实现表达式求值的代码：

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

// 计算表达式
int Calculate(int a, int b, char op)
{
    switch (op) {
    case '+':
n        return a + b;
    case '-':
n        return a - b;
    case '*':
n        return a * b;
    case '/':
n        return a / b;
    }
    return 0;
}

// 表达式求值
int EvaluateExpression(char *exp)
{
    SqStack operandStack, operatorStack;
    InitStack(&operandStack);
    InitStack(&operatorStack);

    int i = 0;
    while (exp[i] != '\0') {
        if (exp[i] == ' ') {
            i++;
            continue;
        }
        else if (isdigit(exp[i])) {
            int num = 0;
            while (isdigit(exp[i])) {
                num = num * 10 + exp[i] - '0';
                i++;
            }
            Push(&operandStack, num);
        }
        else if (isOperator(exp[i])) {
            if (StackEmpty(&operatorStack)) {
                Push(&operatorStack, exp[i]);
            }
            else {
                int topOperator;
                GetTop(&operatorStack, &topOperator);
                if ((exp[i] == '*' || exp[i] == '/') && (topOperator == '+' || topOperator == '-')) {
                    Push(&operatorStack, exp[i]);
                }
                else {
                    int a, b;
                    Pop(&operandStack, &a);
                    Pop(&operandStack, &b);
                    Pop(&operatorStack, &topOperator);
                    int result = Calculate(b, a, topOperator);
                    Push(&operandStack, result);
                    i--;
                }
            }
        }
        else if (exp[i] == '(') {
            Push(&operatorStack, exp[i]);
        }
        else if (exp[i] == ')') {
            int topOperator;
            do {
                Pop(&operatorStack, &topOperator);
                if (topOperator == '(') {
                    break;
                }
                else {
                    int a, b;
                    Pop(&operandStack, &a);
                    Pop(&operandStack, &b);
                    int result = Calculate(b, a, topOperator);
                    Push(&operandStack, result);
                }
            } while (1);
        }
        i++;
    }

    while (!StackEmpty(&operatorStack)) {
        int a, b, topOperator;
        Pop(&operandStack, &a);
        Pop(&operandStack, &b);
        Pop(&operatorStack, &topOperator);
        int result = Calculate(b, a, topOperator);
        Push(&operandStack, result);
    }

    int result;
    Pop(&operandStack, &result);

    return result;
}

五、实验结果

下面是用栈实现表达式求值的实验结果：

请输入表达式：1+2*3-4/2
表达式的值为：6

六、实验总结

本次实验我学习了栈的基本概念和基本操作，掌握了用栈实现表达式求值的方法。在实现栈的基本操作时，我使用了动态内存分配来解决栈大小不够的问题。在实现表达式求值时，我使用了两个栈，一个存储操作数，一个存储运算符。通过本次实验，我对栈的应用有了更深入的了解。