数据结构 | 栈的中缀表达式求值

什么是栈？

栈是一种线性数据结构，具有“先进后出”（Last In First Out, LIFO）的特点。它可以看作是一种受限的线性表，只能在表的一端进行插入和删除操作，这一端被称为栈顶，另一端被称为栈底。不含任何元素的栈称为空栈。

栈的基本操作包括：入栈、出栈、取栈顶元素等。

栈的基本操作

理解栈的基本原理和操作；
掌握栈在表达式求值中的应用。

入栈操作

出栈操作

取栈顶元素

中缀表达式求值

中缀表达式是最常见的表达式表示方式，其表示形式为“操作数1 操作符操作数2”。例如：

3+4

同样表示加法运算，参数分别为3和4，其结果为7。

对于表达式求值，我们通常使用中缀表达式，需要转换为前缀或后缀表达式。转换完成后，可以直接使用栈来求解表达式的值。

实现思路

中缀表达式求值比较复杂，需要考虑运算符的优先级以及括号的影响。因此，我们一般使用栈来实现算法。

具体实现过程如下：

初始化两个栈：运算符栈s1，存储中间结果的栈s2；
从左至右扫描中缀表达式；
遇到操作数时，将其压入s2；
遇到运算符时，比较其与s1栈顶运算符的优先级：
1. 如果s1为空，或栈顶运算符为左括号“（”，则直接将此运算符入栈；
2. 否则，若优先级比栈顶运算符的优先级高，则将运算符压入s1；
3. 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到步骤4-1与s1中新的栈顶运算符相比较；
遇到括号时：
1. 如果是左括号“(”，则直接压入s1；
2. 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃；
3. 重复步骤2-5，直到表达式的最右边；
4. 将s1中剩余的运算符依次弹出并压入s2；
5. 依次弹出s2中的元素计算结果。

我们将使用C语言来实现栈的中缀表达式求值功能。具体步骤如下：

定义栈结构体和相关操作函数（如初始化、入栈、出栈、取栈顶元素等）；
定义字符类型的栈用于存储运算符，定义浮点数类型的栈用于存储操作数和中间结果；
实现后缀表达式求值函数，使用上述算法；
编写主函数，测试中缀表达式求值函数。

具体代码

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct {
    Node *top;
} Stack;

int is_operator(char ch) {
    return (ch == '+' || ch == '-' || ch == '*' || ch == '/');
}

int priority(char op) {
    switch (op) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        default:
            return 0;
    }
}

int calculate(int a, char op, int b) {
    switch (op) {
        case '+':
            return a + b;
        case '-':
            return a - b;
        case '*':
            return a * b;
        case '/':
            return a / b;
        default:
            exit(1);
    }
}

Stack *create_stack() {   // 创建空栈
    Stack *stack = (Stack *)malloc(sizeof(Stack));
    stack->top = NULL;
    return stack;
}

void push(Stack *stack, int data) {   // 入栈操作
    Node *node = (Node *)malloc(sizeof(Node));
    node->data = data;
    node->next = stack->top;
    stack->top = node;
}

int pop(Stack *stack) {   // 出栈操作
    if (stack->top == NULL) {
        return -1;   // 如果栈为空，则返回-1
    }
    Node *node = stack->top;
    int data = node->data;
    stack->top = node->next;
    free(node);
    return data;
}

int top(Stack *stack) {   // 返回栈顶元素
    if (stack->top == NULL) {
        return -1;   // 如果栈为空，则返回-1
    }
    return stack->top->data;
}

/**
 * 计算表达式结果的函数。
 *
 * @param expression 表达式字符串
 * @return 表达式的计算结果
 */
int evaluate_expression(char *expression) {
    Stack *s1 = create_stack();   // 操作数栈，用于存储操作数
    Stack *s2 = create_stack();   // 操作符栈，用于存储操作符

    for (int i = 0; expression[i] != '\0'; i++) {
        if (is_operator(expression[i])) {   // 如果当前字符为操作符
            while (s2->top != NULL && priority(top(s2)) >= priority(expression[i])) {
                // 如果操作符栈不为空，并且栈顶操作符的优先级大于等于当前操作符的优先级
                int b = pop(s1);    // 出栈一个操作数作为运算的右操作数
                int a = pop(s1);    // 再出栈一个操作数作为运算的左操作数
                char op = pop(s2);  // 出栈一个操作符
                int result = calculate(a, op, b);   // 计算两个操作数和操作符的结果
                push(s1, result);   // 将计算结果入栈到操作数栈中
            }
            push(s2, expression[i]);  // 当前操作符入栈到操作符栈中
        } else if (expression[i] == '(') { // 如果当前字符为左括号
            push(s2, expression[i]);    // 入栈到操作符栈中
        } else if (expression[i] == ')') { // 如果当前字符为右括号
            while (top(s2) != '(') {    // 循环执行直到遇到左括号
                int b = pop(s1);    // 出栈一个操作数作为运算的右操作数
                int a = pop(s1);    // 再出栈一个操作数作为运算的左操作数
                char op = pop(s2);  // 出栈一个操作符
                int result = calculate(a, op, b);   // 计算两个操作数和操作符的结果
                push(s1, result);   // 将计算结果入栈到操作数栈中
            }
            pop(s2);    // 弹出左括号
        } else {    // 如果当前字符为数字
            int num = expression[i] - '0';  // 将当前字符转换成数字
            while (expression[i + 1] >= '0' && expression[i + 1] <= '9') {
                // 如果下一个字符也是数字，则将其合并到一起
                num = num * 10 + expression[++i] - '0';
            }
            push(s1, num);  // 将数字入栈到操作数栈中
        }
    }

    // 处理剩余的操作符
    while (s2->top != NULL) {
        int b = pop(s1);    // 出栈一个操作数作为运算的右操作数
        int a = pop(s1);    // 再出栈一个操作数作为运算的左操作数
        char op = pop(s2);  // 出栈一个操作符
        int result = calculate(a, op, b);   // 计算两个操作数和操作符的结果
        push(s1, result);   // 将计算结果入栈到操作数栈中
    }
 
    return pop(s1); // 返回最终的计算结果
}


int main() {
    char expression[100];
    printf("请输入中缀表达式：");
    scanf("%s", expression);
    int result = evaluate_expression(expression);
    printf("计算结果：%d\n", result);
    return 0;
}

文章出处登录后可见！

已经登录？立即刷新