目录
什么是栈？
栈的基本操作
入栈操作
出栈操作
取栈顶元素
中缀表达式求值
实现思路
具体代码
什么是栈？
栈是一种线性数据结构，具有“先进后出”（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;
}
