艺术学校示范校建设专题网站,陕西省档案馆建设网站,有专门做网站的吗,网站开发图片压缩上传报酬目录
什么是栈#xff1f;
栈的基本操作
入栈操作
出栈操作
取栈顶元素
中缀表达式求值
实现思路
具体代码 什么是栈#xff1f;
栈是一种线性数据结构#xff0c;具有“先进后出”#xff08;Last In First Out, LIFO#xff09;的特点。它可以看作是一种受限的…目录
什么是栈
栈的基本操作
入栈操作
出栈操作
取栈顶元素
中缀表达式求值
实现思路
具体代码 什么是栈
栈是一种线性数据结构具有“先进后出”Last In First Out, LIFO的特点。它可以看作是一种受限的线性表只能在表的一端进行插入和删除操作这一端被称为栈顶另一端被称为栈底。不含任何元素的栈称为空栈。 栈的基本操作包括入栈、出栈、取栈顶元素等。
栈的基本操作
理解栈的基本原理和操作掌握栈在表达式求值中的应用。
入栈操作 出栈操作 取栈顶元素 中缀表达式求值
中缀表达式是最常见的表达式表示方式其表示形式为“操作数1 操作符 操作数2”。例如
34
同样表示加法运算参数分别为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.htypedef 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;
}
