当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

解析表达式中栈的应用

发表于: 2014-04-09   作者:crabdave   来源:转载   浏览次数:
摘要: 解析表达式中栈的应用            在有些项目中会涉及到一些表达式解析的操作,各行业有不同的表达式要求,类似于SQL语言一样,一般来说都将行业中的表达式解析出来之后再转换成SQL语句,然后去数据库中进行检索。突然想到算术表达式中的后缀表达式,我觉得可以结合后缀表达式和栈进行设计和开发。   转载一篇文章: &n

解析表达式中栈的应用

 

         在有些项目中会涉及到一些表达式解析的操作,各行业有不同的表达式要求,类似于SQL语言一样,一般来说都将行业中的表达式解析出来之后再转换成SQL语句,然后去数据库中进行检索。突然想到算术表达式中的后缀表达式,我觉得可以结合后缀表达式和栈进行设计和开发。

 

转载一篇文章

 

一.表达式的三种形式: 

    中缀表达式:运算符放在两个运算对象中间,如:(2+1)*3

    后缀表达式:不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行(

 

不再考虑运算符的优先规则,如:2 1 + 3 *

    前缀表达式:同后缀表达式一样,不包含括号,运算符放在两个运算对象的前面,如:* +   2 1 3 

 

二.表达式的转换:       

      将中缀表达式转换为后缀表达式的算法思想: 

       ·数字时,加入后缀表达式;

       ·运算符:

          a. 若为最低级的运算符,入栈; 

          b. 若为 '(',入栈;

          c. 若为 ')',则把栈中的的运算符加入后缀表达式中,直到 '(',从栈中删除'(' ;

          d. 若为不是最低级的运算符,则将从栈顶到第一个优先级不大于(小于,低于或等于)它的运算符(或 '(',

 

但优先满足前一个条件)之间的运算符加入后缀表达式中,该运算符再入栈;

 

>>这句话不好理解,可以说成这样,从栈顶开始,依次弹出比当前处理的运算符优先级高的运算符,直到一个比它优先级

 

低的或者遇到了一个左括号就停止。

 

·当扫描的中缀表达式结束时,栈中的的所有运算符出栈;

 

运用后缀表达式进行计算的具体做法: 

      ·建立一个栈S 

      ·从左到右读后缀表达式,读到数字就将它转换为数值压入栈S中,读到运算符则从栈中依次弹出两个数分别到Y和X

 

,然后以“X   运算符   Y”的形式计算机出结果,再压加栈S中 

     ·如果后缀表达式未读完,就重复上面过程,最后输出栈顶的数值则为结束 

 

三.表达式之间的转换 

    这里我给出一个中缀表达式:a+b*c-(d+e) 

    第一步:按照运算符的优先级对所有的运算单位加括号:式子变成拉:((a+(b*c))-(d+e)) 

    第二步:转换前缀与后缀表达式 

        前缀:把运算符号移动到对应的括号前面 

                    则变成拉:-( +(a *(bc)) +(de)) 

                    把括号去掉:-+a*bc+de 前缀式子出现 

        后缀:把运算符号移动到对应的括号后面 

                    则变成拉:((a(bc)* )+ (de)+ )- 

                    把括号去掉:abc*+de+- 后缀式子出现 

   发现没有,前缀式,后缀式是不需要用括号来进行优先级的确定的。

 

如表达式:3+(2-5)*6/3

 

后缀表达式                            栈

 

3                                           +

 

3                                           +(

 

3 2                                        +(-

 

3 2 5 -                                    +

 

3 2 5 -                                    +*

 

3 2 5 - 6                                  +*/

 

3 2 5 - 6 3                               +*/

 

3 2 5 - 6 3 / * +

 

 

原文章地址:

http://zhidao.baidu.com/link?url=JOPUJQ9HkG5L3j7zhUbaAHTHVBFHahDY1ZhAAYyuQ6PuYHtYbOGjSaCAkUDE0QGEGN28ED6gTYcKWYGehqhAEK

解析表达式中栈的应用

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
程序运行时,我们最好对数据保存到什么地方做到心中有数。特别要注意的是内存的分配。有六个地方都
程序运行时,我们最好对数据保存到什么地方做到心中有数。特别要注意的是内存的分配。有六个地方都
程序运行时,我们最好对数据保存到什么地方做到心中有数。特别要注意的是内存的分配。有六个地方都
本章目标 掌握表达式输出对象的操作; 掌握表达式语言的实际作用,并结合MVC设计模式应用表达式语言
IOS中KVO模式的解析与应用 最近老翁在项目中多处用到了KVO,深感这种模式的好处。现总结如下: 一、
  栈在软件开发中应用非常广泛(函数调用、进制转换、括号匹配问题),记得刚刚毕业那会找工作,面
看了一下《深入java虚拟机》,记录一下书本中的文字。 在Java程序中,每当启用一个线程时,JVM就为
正则表达式在MS SQL Server中的应用 Oracle数据库默认就提供了正则表达式(详见 维基百科)支持,如
栈实现逆波兰表达式 2015-04-05 Lover雪儿 1 //逆波兰表达式 2 #include <stdio.h> 3 #includ
讲解ListView之前,我在这里首先讲解一下观察者模式。 java中的观察者模式,可以使用jdk提供的两个类
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号