【数据结构及算法】1.将表达式转换成逆波兰式

为什么要将看似简单的中序表达式转换为复杂的逆波兰式?原因就在于这个简单是相对人类的思维结构来说的,对计算机而言中序表达式是非常复杂的结构。相对的,逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构,它执行先进后出的顺序。

逆波兰式的意义:(摘自维基)

当有操作符时就计算,因此表达式并不是从右至左整体计算而是每次由中心向外计算一部分,这样在复杂运算中就很少导致操作符错误。

堆栈自动记录中间结果,这就是为什么逆波兰计算器能容易对任意复杂的表达式求值。与普通科学计算器不同,它对表达式的复杂性没有限制。

逆波兰表达式中不需要括号,用户只需按照表达式顺序求值,让堆栈自动记录中间结果;同样的,也不需要指定操作符的优先级。

逆波兰计算器中,没有“等号”键用于开始计算。

逆波兰计算器需要“确认”键用于区分两个相邻的操作数。

机器状态永远是一个堆栈状态,堆栈里是需要运算的操作数,栈内不会有操作符。

教育意义上,逆波兰计算器的使用者必须懂得要计算的表达式的含义。

via 【数据结构及算法】1.将表达式转换成逆波兰式 – KwanChiLeung – 博客园.

  • 浏览:599
  • 评论:0

发表新的回复