[数据结构]表达式运算-后缀表达式

image  

  逆波兰表示法Reverse Polish notationRPN,或逆波兰记法),是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式,在逆波兰记法中,所有操作符置于操作数的后面,因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。

逆波兰结构由弗里德里希·鲍尔(Friedrich L. Bauer)和艾兹格·迪科斯彻在1960年代早期提议用于表达式求值,以利用堆栈结构和减少计算机内存访问。逆波兰记法和相应的算法由澳大利亚哲学家、计算机学家查尔斯·汉布林(Charles Hamblin)在1960年代中期扩充[1][2]

在1960和1970年代,逆波兰记法广泛地被用于台式计算器,因此也在普通公众(工程、商业和金融领域)中使用。

 

算术表达式求值过程是:

• STEP 1:先将算术表达式转换成后缀表达式

• STEP 2:然后对该后缀表达式求值

   下面试着从逻辑上证明以方法A最优。

1.其他想法。

     使用二叉树,首先对表达式解析,一定能使叶子节点为数值而分支节点为运算符。

     如果出现括号匹配可先将配对括号看作数值,加入待处理队列,依次调用主处理函数,解析括号内表达式。

     方法可以实现,但是无论时间复杂度(主要是查找具体字符)

     以及空间复杂度(最后每个非括号字符都将使用一个节点)都是不能与A方法相比的。

     使用递归函数,当字符串增长后,算法稳定性只取决于编译器堆栈是否溢出。

     使用宽度优先搜索,个人感觉比较靠近A方法,但是明显不是最优的(局限于搜索的枚举性)。

 

2.时间复杂度

   假定最优方法时间复杂度为 O(n),   A方法时间复杂度准确的说是 O(2n)~O(n)。

  // 事实上我们可以让STEP 1和 STEP 2同时进行,那么A的时间复杂度已经是最优的。

3. 空间复杂度

空间复杂度不太好说,没有具体的写,大概想了一会,需要考虑自建链栈上限的问题。

4. 具体实施方法

初始化运算符栈op;

将’=’进栈;

从exp读取字符ch;

while (ch!=’\0′)

{ if (ch不为运算符)

将后续的所有数字均依次存放到postexp中;

else

  switch(比较(op栈顶运算符,ch))

  {

      case ‘<‘: //栈顶运算符优先级低

                 将ch进栈; 从exp读取下字符ch; break;

      case ‘=’: //只有栈顶运算符为'(‘,ch为’)’的情况

                退栈; 从exp读取下字符ch; break; 

       case ‘>’: //栈顶运算符应先执行,所以出栈并存放到postexp中

                退栈运算符并将其存放到postexp中; break;

  }

}

若字符串exp扫描完毕,则将运算符栈op中’=’之前的所有运算符依次出栈并存放到postexp中。最后得到后缀表达式postexp;

这里要注意的是,优先级的比较问题,严蔚敏老师的书内貌似分成左右优先级,其实只有两个概念,

一个是栈内元素优先级,一个是栈外元素优先级。

 

运算符

=

(

+

*

/

)

栈内 0 1 3 3 5 5 6
栈外 0 6 2 2 4 4 1
上面的表其实不难理解,总的思路就是用优先级来默认判断进栈出栈。
试几个实例就好,也可以自己推导出来。
 
 

后缀表达式运算这里就不写了,稍稍动手就不难实现。

 
 
此条目发表在未分类分类目录。将固定链接加入收藏夹。

发表评论

邮箱地址不会被公开。 必填项已用*标注