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

目录

什么是栈？

栈的基本操作

入栈操作

出栈操作

取栈顶元素

中缀表达式求值

实现思路

具体代码

---

什么是栈？

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

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

栈的基本操作

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

入栈操作

 

出栈操作

 

取栈顶元素

中缀表达式求值

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

3+4

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

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

实现思路

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

具体实现过程如下：

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

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

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

具体代码

#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;
}