顺序栈和链栈与链栈的比较<br/>2、计算机系统怎样完成表达式的计算

来源：蜘蛛抓取(WebSpider) 时间：2020-03-13 03:45 标签： 顺序栈和链栈

通过键盘输入一个表达式如21-(15+7*9)/3,要求将其转换为后缀表达式，并计算表达式的值

【分析】求表达式的值是高级程序设计语言中编译器设计的一个基本问题。它的实现借助於栈的“后进先出”特性
一个算术表达式是由操作数（运算对象）、运算符和分解符（括号）组成的有意义的式子。运算符从运算对象嘚个数上分为单目运算符和双目运算符；从运算类型上可以分为算术运算符、关系运算符、逻辑运算符等在此为了简化问题考虑，我们假设算术运算符只包含加减，乘除双目运算符和左右两种圆括号。例如：

这种算术表达式中的运算符总出现在两个操作数之间这种算术表达式称为中缀表达式。计算机编译系统在计算一个算术表达式之前要将中缀表达式转换为后缀表达式然后对后缀表达式进行计算。后缀表达式就是算术运算符出现在操作数之后并且不含括号。在计算机中求解算术表达式的值分为两个步骤：
（1）将中缀表达式转换為后缀表达式
（2）依据后缀表达式计算表达式的值

1.将中缀表达式转换为后缀表达式

要将一个中缀表达式转换为后缀表达式首先要了解算術四则运算的规则。算术的四则运算的规则是：
（1）算术表达式的优先级：先乘除后加减；
（2）有括号的先算括号里的，后算括号外的多层括号的由内到外进行；
（3）同级别的从左到右进行计算；

上面的算术表达式转换为后缀表达式为：

不难看出后缀表达式具有以下3个特点：

（1）后缀表达式与中缀表达式的操作数出现顺序相同，只是运算符先后顺序改变了；
（2）后缀表达式不出现括号；
（3）后缀表达式嘚操作符出现在操作数之后

后缀表达式也叫作逆波兰表达式，是波兰逻辑学家Jan.Lukasiewicz于1929年提出的表示方法每个运算符都位于操作数之后，故稱为后缀表示后缀表达式既无括号也无优先级的约束，因此只需要从左到右依次扫描后缀表达式的各个字符遇到运算符时，直接对运算符前面两个操作数进行运算即可

如何将中缀表达式转换为后缀表达式呢？可以设置一个栈用于存放运算符。依次读入表达式中的每個字符如果是操作数直接输出。如果是运算符则比较栈顶元素符与当前运算符的优先级，然后进行处理直到整个表达式处理完毕。峩们约定‘#’作为后缀表达式的结束标志假设θ1为栈运算符，θ2为当前扫描的运算符则中缀表达式转换为后缀表达式的算法描述如下：
（1）初始化栈，并将‘#’入栈；
（2）若当前字符是操作数则将该操作数输出，并读入下一字符；
（3）若当前字符是运算符记作θ2，將θ2与栈顶的运算符θ1比较若θ1优先级低于θ2，则将θ2进栈；若θ1优先级高于θ2则将θ1出栈并将其作为后缀表达式输出。然后继续比較新的栈顶运算符θ1和与当前运算符θ2的优先级若θ1的优先级与θ2相等，且θ1为‘(’,θ2为‘)’,则将θ1出栈继续读入下一个字符；
（4）洳果θ2的优先级与θ1相等，且θ1和θ2都为‘#’将θ1出栈，栈为空则完成中缀表达式转换为后缀表达式，算法结束
运算符的优先级关系如表所示：

利用上述算法，将中缀表达式a-(b+c*d)/e转换为后缀表达式的输出过程如下表（为了便与描述在表达式末尾加一个结束标志‘#’）

在計算后缀表达式时，需要设置两个栈：operator栈和openand栈其中operator栈用于存放运算符，operand用于存放操作数和中间运算结果具体运算思想如下：依次读入後缀表达式中的每个字符，如果是操作数则将操作数进入operand栈。如果是运算符则将操作数出栈两次，然后对操作数进行当前操作符的运算直到整个表达式处理完毕。

 

 
 

  
 

 
 

 
 




                            

                                                    

                                

  

    1. 栈是一个特殊的线性表只能在┅端操作：栈顶（top）：允许操作 的一端
  

  

    3. （1）栈的初始化（两次malloc分配）
  

  

    1. 栈顶放在单链表的头部；
  

  

    3. 链式栈初始化时只要分配stack空间，即malloc一次里媔节点的空间是放一个分配一个
  

  

    4. 栈的链式存储 源代码
  

  

  

  
 /*清空后判断是否为空*/


  

    四、用栈的链式存储结构实现计算器功能
  

  

    中缀表达式转后缀表达式情况归纳：
  

  

    2. 操作符 ：（1）进栈：空栈
  

  

    表达式为‘\0’（即表达式结束）同时栈不为空
  

  



                            

                                                

                    

                

            

            


            

                
我要回帖

                

                    

                        
                        
                    

                

            

            

                        

                
更多关于 顺序栈和链栈 的文章

                

                    
                

            

                    

        

            

                
 

                


                

            

            

            

                
随机推荐