ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

快捷登录

搜索
EH技术汇-专业的职场技能充电站 妙哉!函数段子手趣味讲函数 Excel服务器-会Excel,做管理系统 Excel Home精品图文教程库
HR薪酬管理数字化实战 Excel 2021函数公式学习大典 Excel数据透视表实战秘技 打造核心竞争力的职场宝典
300集Office 2010微视频教程 数据工作者的案头书 免费直播课集锦 ExcelHome出品 - VBA代码宝免费下载
用ChatGPT与VBA一键搞定Excel WPS表格从入门到精通 Excel VBA经典代码实践指南
查看: 3043|回复: 17

逆波兰表达式简单演示

[复制链接]

TA的精华主题

TA的得分主题

发表于 2014-6-13 00:04 | 显示全部楼层 |阅读模式
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册
本帖已被收录到知识树中,索引项:其他结构和算法
摘自维基百科:http://zh.wikipedia.org/wiki/%E9%80%86%E6%B3%A2%E5%85%B0%E8%A1%A8%E7%A4%BA%E6%B3%95
逆波兰表示法Reverse Polish notationRPN,或逆波兰记法),是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式,在逆波兰记法中,所有操作符置于操作数的后面,因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。
逆波兰结构由弗里德里希·鲍尔(Friedrich L. Bauer)和艾兹格·迪科斯彻在1960年代早期提议用于表达式求值,以利用堆栈结构和减少计算机内存访问。逆波兰记法和相应的算法澳大利亚哲学家计算机学家查尔斯·汉布林(Charles Hamblin)在1960年代中期扩充[1][2]
在1960和1970年代,逆波兰记法广泛地被用于台式计算器,因此也在普通公众(工程商业金融领域)中使用。

逆波兰记法中,操作符置于操作数的后面。例如表达“三加四”时,写作“3 4 +”,而不是“3 + 4”。如果有多个操作符,操作符置于第二个操作数的后面,所以常规中缀记法的“3 - 4 + 5”在逆波兰记法中写作“3 4 - 5 +”:先3减去4,再加上5。使用逆波兰记法的一个好处是不需要使用括号。例如中缀记法中“3 - 4 * 5”与“(3 - 4)*5”不相同,但后缀记法中前者写做“3 4 5 * -”,无歧义地表示“3 (4 5 *) −”;后者写做“3 4 - 5 *”。
逆波兰表达式的解释器一般是基于堆栈的。解释过程一般是:操作数入栈;遇到操作符时,操作数出栈,求值,将结果入栈;当一遍后,栈顶就是表达式的值。因此逆波兰表达式的求值使用堆栈结构很容易实现,和能很快求值。
注意:逆波兰记法并不是简单的波兰表达式的反转。因为对于不满足交换律的操作符,它的操作数写法仍然是常规顺序,如,波兰记法“/ 6 3”的逆波兰记法是“6 3 /”而不是“3 6 /”;数字的数位写法也是常规顺序。

TA的精华主题

TA的得分主题

 楼主| 发表于 2014-6-13 00:06 | 显示全部楼层
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册
附件是简单的逆波兰表达式的转换。

nibolanDemo.rar

26.35 KB, 下载次数: 28

TA的精华主题

TA的得分主题

 楼主| 发表于 2014-6-13 00:11 | 显示全部楼层
学习逆波兰表达式的难点在对操作符的优先级的判断和入队,理解了这点后面的路子就容易走了。
主要代码:
  1. Public Sub nibolang()
  2.     Dim str As String
  3.     Dim iLen As Long, i As Long
  4.     Dim v As Variant, x As Variant
  5.     Dim isp As Long '栈内优先级变量
  6.     Dim icp As Long '栈外优先级变量
  7.     Dim sh As Worksheet
  8.     Dim rng As Range
  9.     Dim cStack As clsStack
  10.     Dim cQueue As clsQueue
  11.     Dim m As Long
  12.     Dim cStackRng As clsStackRange
  13.     Dim cQueueRng As clsQueueRange
  14.    
  15.     Set cStackRng = New clsStackRange '临时类用于模拟栈
  16.     Set cQueueRng = New clsQueueRange '临时类 用于模拟队列
  17.     Set cStack = New clsStack
  18.     Set cQueue = New clsQueue
  19.    
  20.     Set sh = Sheets("sheet1")
  21.     With sh
  22.         Set rng = .Cells(1, 1)
  23.         str = rng.Value
  24.         Set rng = .Cells(7, 9)
  25.         rng.Value = ""
  26.     End With
  27.     iLen = Len(str)
  28.     cStack.InitializeClass iLen
  29.     cQueue.InitializeClass iLen
  30.     cStackRng.initStackRange iLen
  31.     cQueueRng.initQueueRange iLen
  32.     For i = 1 To iLen
  33.         v = Mid(str, i, 1)
  34.         If CheckNumber(v) Then
  35.             '操作数直接入队
  36.             cQueue.Push v
  37.             cQueueRng.setColor
  38.             cQueueRng.Push v
  39.         Else
  40.             '操作符需与栈顶元素比较优先级
  41.             icp = cStack.getOp(v)
  42.             If icp = 8 Then
  43.                 '左括号直接入栈
  44.                 cStack.Push v, icp
  45.                 cStackRng.Push v, icp
  46.                 cStackRng.setColor
  47.                
  48.             ElseIf icp = 2 Then '右括号栈内操作符出栈
  49.                 Do Until cStack.Peek = 8 '直到左括号
  50.                     x = cStack.Pop
  51.                     cStackRng.setColor
  52.                     cStackRng.Pop
  53.                     cQueue.Push x '压入队列,
  54.                     cQueueRng.setColor
  55.                     cQueueRng.Push x
  56.                 Loop
  57.                 cStack.ReMove '丢弃左括号
  58.                 cStackRng.Pop
  59.             Else
  60.                 isp = cStack.Peek
  61.                 If isp = 8 Then
  62.                     '栈顶是左括号直接入栈
  63.                     cStack.Push v, icp
  64.                     cStackRng.setColor
  65.                     cStackRng.Push v, icp
  66.                 Else
  67.                     If isp >= icp Then '栈内优先级大于等于栈外优先级,出栈
  68.                         Do
  69.                             x = cStack.Pop
  70.                             cStackRng.setColor
  71.                             cStackRng.Pop
  72.                             cQueueRng.setColor
  73.                             cQueue.Push x
  74.                             cQueueRng.Push x
  75.                            
  76.                             isp = cStack.Peek
  77.                             If isp = 0 Then
  78.                                 Exit Do '栈空
  79.                             ElseIf isp = 8 Then
  80.                                 Exit Do '左括号
  81.                             End If
  82.                         Loop Until isp >= icp
  83.                         cStack.Push v, icp '操作符入栈
  84.                         cStackRng.setColor
  85.                         cStackRng.Push v, icp
  86.                     Else
  87.                         cStack.Push v, icp '栈外操作符大于栈内操作符,操作符入栈
  88.                         cStackRng.setColor
  89.                         cStackRng.Push v, icp
  90.                         
  91.                     End If
  92.                 End If
  93.             End If
  94.         End If
  95.     Next i
  96.     Do Until cStack.Peek = 0
  97.         '操作符栈,出栈
  98.         x = cStack.Pop
  99.         cStackRng.setColor
  100.         cStackRng.Pop
  101.         '入队
  102.         cQueue.Push x
  103.         cQueueRng.setColor
  104.         cQueueRng.Push x
  105.     Loop
  106.     m = ExecuNiBolan(cQueue)
  107.     With sh
  108.         Set rng = .Cells(7, 9)
  109.         rng.Value = m
  110.     End With

  111. End Sub
复制代码

TA的精华主题

TA的得分主题

 楼主| 发表于 2014-6-13 00:15 | 显示全部楼层
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册
用Range对象模拟栈和队列,便于理解数据结构。
nibolan.png

TA的精华主题

TA的得分主题

 楼主| 发表于 2014-6-13 00:22 | 显示全部楼层
例子[编辑]
中缀表达式“5 + ((1 + 2) * 4) − 3”写作

5 1 2 + 4 * + 3 −
下表给出了该逆波兰表达式从左至右求值的过程,堆栈栏给出了中间值,用于跟踪算法。

输入        操作        堆栈        注释
5        入栈        5
1        入栈        5, 1
2        入栈        5, 1, 2
+        加法运算        5, 3        (1, 2)出栈;将结果(3)入栈
4        入栈        5, 3, 4
*        乘法运算        5, 12        (3, 4)出栈;将结果(12)入栈
+        加法运算        17        (5, 12)出栈;将结果 (17)入栈
3        入栈        17, 3
−        减法运算        14        (17, 3)出栈;将结果(14)入栈
计算完成时,栈内只有一个操作数,这就是表达式的结果:14

评分

1

查看全部评分

TA的精华主题

TA的得分主题

发表于 2014-6-13 08:30 | 显示全部楼层
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册
不明觉厉!!!!!!!帮顶

TA的精华主题

TA的得分主题

发表于 2014-6-13 09:58 | 显示全部楼层
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册
除了省却了括号,其它似乎也没啥。

当然可能在计算机处理时速度会更快一些。

TA的精华主题

TA的得分主题

 楼主| 发表于 2014-6-13 10:21 | 显示全部楼层
香川群子 发表于 2014-6-13 09:58
除了省却了括号,其它似乎也没啥。

当然可能在计算机处理时速度会更快一些。

我觉得关键点是,把复杂的问题简化分割成简单的处理方式。

TA的精华主题

TA的得分主题

发表于 2014-6-13 11:11 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助
本帖最后由 香川群子 于 2014-6-13 11:16 编辑

用这个函数可以计算你的【逆波兰表达式】
  1. Function f(txt)
  2.     s = Split(Trim(txt)) '去除逆波兰表达式的多余空格后拆分为数组s
  3.     f = dgjs(s) '调用递归计算
  4. End Function

  5. Function dgjs(s) '递归计算过程
  6.     If UBound(s) = 2 Then '如果数组中只剩最后3个时
  7.         dgjs = Application.Evaluate(s(0) & s(2) & s(1)) '直接计算返回计算结果
  8.     Else
  9.         ReDim r(UBound(s) - 2) '每次重新定义一个少2个元素的数组r
  10.         For i = 0 To UBound(r) '检查直到非数值即运算符号时停止
  11.             If Not IsNumeric(s(i + 2)) Then Exit For Else r(i) = s(i) '数值移动到新数组r
  12.         Next
  13.         r(i) = Application.Evaluate(s(i) & s(i + 2) & s(i + 1)) '计算这一部的结果并存入新数组
  14.         '注意每一次【n1 n2 f = n】3个变量运算后合并为一个变量,结果都会减少2个变量。
  15.         For i = i + 1 To UBound(r) '继续把未结束的剩余部分搬迁到新数组
  16.             r(i) = s(i + 2)
  17.         Next
  18.         dgjs = dgjs + dgjs(r) '继续下一层的递归计算
  19.     End If
  20. End Function
复制代码
呵呵。

TA的精华主题

TA的得分主题

发表于 2014-6-13 11:38 | 显示全部楼层
我设想如下逆波兰表达式:
1 2 3 4 5 + * - +

计算过程应该等价于:
     1 2 3 4 5 + * - +   
→  1 2 3 (4+5) * - +
→  1 2 3*(4+5) - +
→  1 2-3*(4+5) +
→  1+2-3*(4+5)

而这样的计算式的逆波兰表达式应该是:
1 2 + 3 4 5 + * -

因此真正对应【1 2 3 4 5 + * - +】的原始算式应该是:
1+(2-3*(4+5))
您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

手机版|关于我们|联系我们|ExcelHome

GMT+8, 2024-3-28 18:16 , Processed in 0.058629 second(s), 11 queries , Gzip On, Redis On.

Powered by Discuz! X3.4

© 1999-2023 Wooffice Inc.

沪公网安备 31011702000001号 沪ICP备11019229号-2

本论坛言论纯属发表者个人意见,任何违反国家相关法律的言论,本站将协助国家相关部门追究发言者责任!     本站特聘法律顾问:李志群律师

快速回复 返回顶部 返回列表