什么是栈？
栈是一种线性数据结构，具有“先进后出”（Last In First Out, LIFO）的特点。它可以看作是一种受限的线性表，只能在表的一端进行插入和删除操作，这一端被称为栈顶，另一端被称为栈底。不含任何元素的栈称为空栈。
栈的基本操作包括：入栈、出栈、取栈顶元素等。
栈的基本操作
- 理解栈的基本原理和操作；
- 掌握栈在表达式求值中的应用。
入栈操作
出栈操作
取栈顶元素
中缀表达式求值
中缀表达式是最常见的表达式表示方式，其表示形式为“操作数1 操作符 操作数2”。例如：
3+4
同样表示加法运算，参数分别为3和4，其结果为7。
对于表达式求值，我们通常使用中缀表达式，需要转换为前缀或后缀表达式。转换完成后，可以直接使用栈来求解表达式的值。
实现思路
中缀表达式求值比较复杂，需要考虑运算符的优先级以及括号的影响。因此，我们一般使用栈来实现算法。
具体实现过程如下：
- 初始化两个栈：运算符栈s1，存储中间结果的栈s2；
- 从左至右扫描中缀表达式；
- 遇到操作数时，将其压入s2；
- 遇到运算符时，比较其与s1栈顶运算符的优先级：
- 如果s1为空，或栈顶运算符为左括号“（”，则直接将此运算符入栈；
- 否则，若优先级比栈顶运算符的优先级高，则将运算符压入s1；
- 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到步骤4-1与s1中新的栈顶运算符相比较；
- 遇到括号时：
- 如果是左括号“(”，则直接压入s1；
- 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃；
- 重复步骤2-5，直到表达式的最右边；
- 将s1中剩余的运算符依次弹出并压入s2；
- 依次弹出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; }
