当前位置: 首页> 游戏> 评测 > 昆山网页设计公司_黔东南网页制作_最新新闻摘抄_快速排名刷

昆山网页设计公司_黔东南网页制作_最新新闻摘抄_快速排名刷

时间:2025/7/10 4:36:46来源:https://blog.csdn.net/qiwsir/article/details/146359230 浏览次数:1次
昆山网页设计公司_黔东南网页制作_最新新闻摘抄_快速排名刷

在严蔚敏教授的《数据结构》(人民邮电出版社,2015年2月第2版)案例 3.3:表达式求值(第78页)中,对后缀表达式求值有详细叙述,但其内容令部分基础不足够好的学习者费解,为此,本节先以简单的形式对后缀表达式求值方法给予介绍,而后解释书中的难点。

1. 初步理解

后缀表达式的求值过程是:从左到右扫描后缀表达式 postexp

  • 若读取的是一个操作数,将它压入操作数栈;
  • 若读取的是一个运算符 op,从操作数栈中连续出栈两个操作数,假设为 a(第 1个出栈元素)和 b(第 2 个出栈元素),计算 b op a 的值,并将计算结果进操作数栈。
  • 当整个后缀表达式扫描结束时,操作数栈中的栈顶元素就是表达式的计算结果。

以中缀表达式 (56 - 20) / (4 + 2) 为例,它对应的后缀表达式为 56 20 - 4 2 + / ,如果利用栈,扫描这个后缀表达式 56 20 - 4 2 + / ,求值过程如下(Opnd 是操作数栈):

操作Opnd 栈(栈底→栈顶)
遇到 56,将其进栈56
遇到 20,将其进栈56, 20
遇到 -,依次将 20、56 出栈,计算 56-20=36,将结果 36 进栈36
遇到 4,将其进栈36, 4
遇到 2,将其进栈36, 4, 2
遇到 +,依次将 2、4 出栈,计算 4+2=6,将结果 6 进栈36, 6
遇到 /,依次将 6, 36 出栈,计算 36/6=6,将结果 6 进栈6
postexp 扫描完毕,算法结束,栈顶数值 6 即为所求。

【算法步骤】

while(从 postexp 读取字符 ch,ch != '\0'){ch 为 + : 从 Opnd 中出栈两个数值 a 和 b,计算 b+a=c; 将 c 进栈;ch 为 - : 从 Opnd 中出栈两个数值 a 和 b,计算 b-a=c; 将 c 进栈;ch 为 * : 从 Opnd 中出栈两个数值 a 和 b,计算 b*a=c; 将 c 进栈;ch 为 / : 从 Opnd 中出栈两个数值 a 和 b,若 a 不为零,计算 b/a=c; 将 c 进栈;ch 为数字字符 : 将连续的数字串转换成整数 d,将 d 进栈;
}

【算法描述】

double comp_value(char * postexp){double d, a, b, c, e;SqStack * Opnd; //操作数栈,顺序栈InitStack(Opnd); while(*postexp != '\0'){//postexp字符未扫描完毕,循环switch(*postexp){case '+':Pop(Opnd, a);Pop(Opnd, b);c = b + a;Push(Opnd, c);break;case '-':Pop(Opnd, a);Pop(Opnd, b);c = b - a;Push(Opnd, c);break;case '*':Pop(Opnd, a);Pop(Opnd, b);c = b * a;Push(Opnd, c);break;case '/':Pop(Opnd, a);Pop(Opnd, b);if(a != 0){c = b / a;Push(Opnd, c);break;} else {printf("\n\t零不能做分母\n");exit(0);}break;default:d = 0; //将连续的数字字符转换成对应的数值存放到 dwhile(*postexp >= '0' && *postexp <= '9'){d = 10 * d + *postexp - '0';postexp++;}Push(Opnd, d);break;}postexp++;}GetTop(Opnd, e);DestroyStack(Opnd);return e;
}

由上可知:

  1. 栈自动记录中间结果,容易对任意复杂的表达式求值。
  2. 后缀表达式中不需要括号,只需按照表达式顺序求值,让栈自动记录中间结果;也不需要指定操作符的优先级。
  3. 机器状态永远是一个栈状态,栈里是需要运算的操作数,栈内不会有操作符。

2. 理解教材的案例

严蔚敏教授在《数据结构》(人民邮电出版社,2015年2月第2版)案例 3.3 中,给出了一个运算符优先关系表,如下表所示:

在这里插入图片描述

表中显示了运算符之间的三种关系:

  • θ 1 < θ 2 \theta_1\lt\theta_2 θ1<θ2 θ 1 \theta_1 θ1 的优先权低于 θ 2 \theta_2 θ2 ,例如: ′ + ′ < ′ ∗ ′ ; ′ + ′ < ′ / ′ ; '+'\lt'*';~'+'\lt'/';~ +<; +</;  即“先乘除、后加减”的运算规则。
  • θ 1 = θ 2 \theta_1=\theta_2 θ1=θ2 θ 1 \theta_1 θ1 的优先权等于 θ 2 \theta_2 θ2 。注意:先出现的运算符优先级高,所以有: ′ + ′ > ′ + ′ ; ′ − ′ > ′ − ′ ; '+'\gt'+';~'-'\gt'-';~ +>+; >;  等。
  • θ 1 > θ 2 \theta_1\gt\theta_2 θ1>θ2 θ 1 \theta_1 θ1优先权高于 θ 2 \theta_2 θ2 ,括号内的优先级高,+、-、*、/ θ 1 \theta_1 θ1 时的优先性均低于 ( ,但高于 )
  • 表中的“( = )”表示当左右括号相遇时,括号内的运算已经完成。
  • 为了便于实现,假设每个表达式均以 # 开始,以 # 结束。所以 # = # 表示整个表达式求值完毕。
  • 表中空白的部分,即 )(#) 、以及 (# 之间无优先关系,这是因为表达式中不允许它们相继出现,一旦遇到这种情况,则可以认为出现了语法错误。

为了实现上述算符优先算法,设置两个栈:

  • 寄存运算符的栈,命名为 Optr
  • 寄存操作数或运算结果的栈,命名为 Opnd

【算法步骤】

  1. 初始化 Optr 栈和 Opnd ,将表达式起始符 # 压入 Optr 栈。
  2. 扫描表达式,读入第一个字符 ch,如果表达式没有扫描完毕至 #Optr 的栈顶元素不为 # 时,则循环执行以下操作:
    • ch 不是运算符,则压入 Opnd 栈,读入下一字符 ch
    • ch 是运算符,则根据 Optr 的栈顶元素和 ch 的优先级比较结果,做不同的处理:
      • 若是小于,则 ch 压入 Optr 栈,读入下一字符 ch
      • 若是大于,则弹出 Optr 栈顶的运算符,从 Opnd 栈弹出两个数,进行相应运算,结果压入 Opnd 栈;
      • 若是等于,则 Optr 的栈顶元素是 ( 且 ch 是 ),这时弹出 Optr 栈顶的 ( ,相当于括号匹配成功,然后读入下一字符 ch
  3. Opnd 栈顶元素即为表达式求值结果,返回此元素。

【算法描述】

char EvaluateExpression(){//算术表达式求值的算符优先算法,设 OPTR 和 OPND 分别为运算符栈和操作数栈Initstack(Opnd); //初始化 Opnd 栈Initstack(Optr); //初始化 Optr 栈Push(Optr, '#'); //将表达式起始符 '#' 压入 Optr 栈cin>>ch;while(ch !='#' || GetTop(Optr) !='#'){//表达式没有扫描完毕或 Optr 的栈顶元素不为 '#'if(!In(ch)){ //ch 不是运算符则进 Opnd 栈Push(Opnd, ch);cin>>ch;} else{switch(Precede(GetTop(Optr), ch))  //比较 Optr 的栈顶元素和 ch 的优先级case '<':Push(Optr, ch);//当前字符 ch 压入 Optr 栈,cin>>ch; //读入下一字符 chbreak;case '>':Pop(Optr, theta); //弹出 Optr 栈顶的运算符Pop(Opnd, b);  //弹出 Opnd 栈顶的两个操作数Pop(Opnd, a);Push(Opnd, Operate(a, theta, b)); //将运算结果压入 Opnd 栈break;case '=': //Optr 的栈顶元素是 '(' 且 ch 是 ')'Pop(Optr, x); //弹出 Optr 栈顶的 '('cin>>ch; //读入下一字符 chbreak;}}return GetTop(OPND); //Opnd 栈顶元素即为表达式求值结果
}

上述算法描述中使用到了三个函数:

  • 第 9 行出现的函数 In() ,用于判定读入的字符 ch 是否为运算符;
  • 第 13 行出现的函数 Precede() ,用于判定运算符栈的栈顶元素与读入的运算符之间优先关系;
  • 第 22 行出现的函数 Operate() 用于进行二元运算。

【算法分析】

  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( n ) O(n) O(n)
关键字:昆山网页设计公司_黔东南网页制作_最新新闻摘抄_快速排名刷

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: