【PB】实现表达式计算的两个步骤

cyycoish

最近在研究表达式的处理，顺手写了这么一款小程序。
为了实现表达式计算，本程序使用了两个步骤：1.中缀转后缀 2.计算后缀表达式（逆波兰式）
表达式支持 + - * / \ ^ 共6中运算符分别为 加、减、乘、除、模、幂。均是标准的双目运算符。
输入一个中缀表达式，形如 “1+1”程序可以自动转换为相应后缀表达式“1 1 +”
在中缀表达式之前加“@”符号，可以计算该中缀表达式。在逆波兰式之前加“#”可以计算逆波兰
式的值。支持小数，负数，括号。{} 花括号 [] 方括号 （） 圆括号 可以混搭。
程序可以识别 括号不匹配 非法字符 缺少运算符 缺少操作数 4 种错误。
下面上图：


原理如下：

该程序由powerbasic10 编译而成 源代码：
header.bi

1. MACRO CONST = MACRO
   
2. CONST N = 100 '数栈大小
   
3. CONST M = 100 '符栈大小
   
4. CONST O = 6   '运算符个数
   
5. 
   
6. GLOBAL ERRNUM   AS INTEGER '错误标识符
   
7. GLOBAL ScanIdx  AS LONG    '扫描索引
   
8. 
   
9. TYPE OPRTYPE              '运算符
   
10.     opname AS STRING * 10 '运算符字符串表示
    
11.     level  AS INTEGER     '运算符优先级
    
12.     index  AS INTEGER     '运算符标识
    
13. END TYPE
    
14. 
    
15. TYPE NUMSTACK           '数栈定义
    
16.     stack(N) AS DOUBLE  '数栈栈体
    
17.     top      AS INTEGER '数栈栈顶
    
18. END TYPE
    
19. 
    
20. TYPE OPRSTACK           '符栈定义
    
21.     stack(M) AS OPRTYPE '符栈栈体
    
22.     top      AS INTEGER '符栈栈顶
    
23. END TYPE
    
24. 
    
25. GLOBAL Oper() AS OPRTYPE '运算符表
    
26. 
    
27. SUB InitNumStack(BYREF numStk AS NUMSTACK) '数栈初始化
    
28.     numStk.top = 0 '栈顶为0栈为空
    
29. END SUB
    
30. 
    
31. SUB PushNum(BYREF numStk AS NUMSTACK, BYVAL v AS DOUBLE) '数栈压栈
    
32.     IF numStk.top = N - 1 THEN '若数栈达到存贮上限
    
33.         ERRNUM = 1 '溢出报错
    
34.     ELSE
    
35.         numStk.top = numStk.top + 1 '向上堆
    
36.         numStk.stack(numStk.top) = v '数字进栈
    
37.     END IF
    
38. END SUB
    
39. 
    
40. SUB PopNum(BYREF numStk AS NUMSTACK, BYREF v AS DOUBLE) '数栈出栈
    
41.     IF numStk.top = 0 THEN '若栈空
    
42.         ERRNUM = 5 '数栈触底报错
    
43.     ELSE
    
44.         v = numStk.stack(numStk.top) '数字出栈
    
45.         numStk.top = numStk.top - 1 '向下落
    
46.     END IF
    
47. END SUB
    
48. 
    
49. SUB InitOprStack(BYREF oprStk AS OPRSTACK) '符栈初始化
    
50.     oprStk.top = 0 '设栈空
    
51. END SUB
    
52. 
    
53. SUB PushOpr(BYREF oprStk AS OPRSTACK, BYVAL sign AS OPRTYPE) '符栈压栈
    
54.     IF oprStk.top = M THEN '达到上限
    
55.         ERRNUM = 1 '符栈溢出
    
56.     ELSE
    
57.         oprStk.stack(oprStk.top) = sign '操作符进栈
    
58.         oprStk.top = oprStk.top + 1 '向上堆
    
59.     END IF
    
60. END SUB
    
61. 
    
62. SUB PopOpr(BYREF oprStk AS OPRSTACK, BYREF rtn AS OPRTYPE) '符栈出栈
    
63.     IF oprStk.top = 0 THEN
    
64.         ERRNUM = 2 '符栈触底
    
65.     ELSE
    
66.         oprStk.top = oprStk.top - 1 '符栈向下落
    
67.         rtn.opname = TRIM$(oprStk.stack(oprStk.top).opname) '出栈
    
68.         rtn.level = oprStk.stack(oprStk.top).level
    
69.         rtn.index = oprStk.stack(oprStk.top).index
    
70.     END IF
    
71. END SUB
    
72. 
    
73. SUB PeekOpr(BYVAL oprStk AS OPRSTACK, BYREF rtn AS OPRTYPE) '看符栈栈顶
    
74.     IF oprStk.top > 0 THEN '若符栈不为空
    
75.         rtn.opname = TRIM$(oprStk.stack(oprStk.top - 1).opname) '传递栈顶运算符参数
    
76.         rtn.level = oprStk.stack(oprStk.top - 1).level
    
77.         rtn.index = oprStk.stack(oprStk.top - 1).index
    
78.     END IF
    
79. END SUB
    
80. 
    
81. SUB InitOprTable() '初始化运算符表
    
82.     DIM Oper(O) AS GLOBAL OPRTYPE '初始化运算符表载体数组
    
83.     Oper(0).opname = "+": Oper(0).level =  1: Oper(0).index = 1
    
84.     Oper(1).opname = "*": Oper(1).level =  2: Oper(1).index = 2
    
85.     Oper(2).opname = "/": Oper(2).level =  2: Oper(2).index = 3
    
86.     Oper(3).opname = "": Oper(3).level =  2: Oper(3).index = 4
    
87.     Oper(4).opname = "^": Oper(4).level =  3: Oper(4).index = 5
    
88.     Oper(5).opname = "(": Oper(5).level = -1: Oper(5).index = 6
    
89.     Oper(6).opname = ")": Oper(6).level = -1: Oper(6).index = 7
    
90.     '运算符名称           运算符优先级        运算符索引标识
    
91. END SUB
    
92. 
    
93. FUNCTION HandelOpr(BYVAL a AS DOUBLE, BYVAL b AS DOUBLE, BYVAL index AS INTEGER) AS DOUBLE '定义运算符运算过程
    
94.     LOCAL ans AS DOUBLE '定义运算结果
    
95.     SELECT CASE index '按索引区分运算符
    
96.     CASE 1 '加法运算
    
97.         ans = a + b
    
98.     CASE 2 '乘法运算
    
99.         ans = a * b
    
100.     CASE 3 '除法运算
     
101.         ans = a / b
     
102.     CASE 4 '取模运算
     
103.         ans = a MOD b
     
104.     CASE 5 '幂运算
     
105.         ans = a ^ b
     
106.     END SELECT
     
107.     FUNCTION = ans '函数返回值
     
108. END FUNCTION
     
109. 
     
110. FUNCTION IsOper(BYREF oprStk AS OPRSTACK, BYVAL s AS STRING, BYREF level AS INTEGER, _
     
111.                 BYREF ioper AS OPRTYPE) AS INTEGER '判定是否为运算符函数
     
112.     LOCAL i AS INTEGER
     
113.     FUNCTION = 0
     
114.     FOR i = 0 TO O '遍历运算符表
     
115.         IF s = TRIM$(oper(i).opname) THEN '找到相似运算符
     
116.             level = oper(i).level '传递运算符优先级
     
117.             ioper = oper(i) '传递运算符本身
     
118.             FUNCTION = oper(i).index '返回运算符索引标识
     
119.             EXIT FUNCTION '退出函数
     
120.         END IF
     
121.     NEXT
     
122. END FUNCTION
     
123. 
     
124. FUNCTION PreProcessor(BYVAL str AS STRING) AS STRING '预处理器
     
125.     str = TRIM$(str) '去入口字符串两端空格
     
126.     REPLACE "-" WITH "+-" IN str '将减去一个数变为加上一个数的相反数
     
127.     REPLACE ANY "{[" WITH "((" IN str '将左括号统一
     
128.     REPLACE ANY "}]" WITH "))" IN str '统一右侧括号
     
129.     IF LEFT$(str, 2) = "+-" THEN str = MID$(str, 2) '如果表达式第一个数为负数,消除替换符号后的副作用
     
130.     FUNCTION = str '返回处理完毕后的字符串
     
131. END FUNCTION
     
132. 
     
133. SUB Compute(BYREF xp AS STRING) '将源表达式转为逆波兰式
     
134.     LOCAL oprStk AS OPRSTACK '定义符栈
     
135.     LOCAL opr0   AS OPRTYPE  '定义临时操作符1
     
136.     LOCAL opr    AS OPRTYPE  '定义临时操作符2
     
137.     LOCAL tmpEle AS STRING   '临时表达式元素
     
138.     LOCAL tmpXp  AS STRING   '临时表达式
     
139.     LOCAL i  AS INTEGER      '计数器
     
140.     LOCAL j  AS INTEGER      '计数器
     
141.     LOCAL nb AS INTEGER      '为数字时该值为1,否则为0
     
142.     LOCAL l  AS INTEGER      '临时存放优先级
     
143.     LOCAL p  AS STRING       '临时存放空格
     
144. 
     
145.     ScanIdx = 0               '初始扫描索引
     
146.     CALL InitOprTable()       '初始化运算符表
     
147.     CALL InitOprStack(oprStk) '初始化符栈
     
148. 
     
149.     xp = PreProcessor(xp)     '预处理表达式字符串
     
150. 
     
151.     FOR i = 1 TO LEN(xp) '从预处理后的表达式开始到结束
     
152.         ScanIdx = i: tmpEle = "" '设置扫描索引,临时元素设空
     
153.         tmpEle = TRIM$(tmpEle & MID$(xp, i, 1))
     
154.         nb = 1 '数字标记为真
     
155.         IF IsOper(oprStk, tmpEle, l, opr0) = 0 THEN '若不是运算符
     
156.             FOR j = 1 TO LEN(tmpEle) '逐个扫描元素
     
157.                 LOCAL char AS INTEGER
     
158.                 char = ASC(MID$(tmpEle, j, 1)) '记录元素内各个字符的asc码
     
159.                 IF (char >= 48 AND char <= 57) OR char = 46 OR char = 45 THEN '如果是数字,小数点,负号
     
160.                     nb = 1 '数字标记为真
     
161.                 ELSE '否则
     
162.                     nb = 0 '数字标记为假
     
163.                     EXIT FOR '不是数字立即退出循环
     
164.                 END IF
     
165.             NEXT
     
166.             IF nb = 1 THEN tmpXp = tmpXp & p & tmpEle: p = "" '将数字存入临时逆波兰式
     
167.         ELSEIF IsOper(oprStk, tmpEle, l, opr0) >= 1 AND nb = 1 THEN '如果前一个为数字,当前为运算符
     
168.             IF opr0.index <> 6 AND opr0.index <> 7 THEN '如果不是括号
     
169.                 CALL PeekOpr(oprStk, opr) '看符栈栈顶
     
170.                 WHILE opr.level >= opr0.level AND oprStk.top > 0 '当当前运算符优先级大于等于栈顶优先级并且符栈不为空
     
171.                     CALL PopOpr(oprStk, opr) '出栈一个运算符
     
172.                     tmpXp = tmpXp & " " & TRIM$(opr.opname) & " " '将运算符存入逆波兰式
     
173.                     CALL PeekOpr(oprStk, opr) '再看符栈栈顶
     
174.                 WEND
     
175.                 CALL PushOpr(oprStk, opr0) '将当前运算符压入符栈
     
176.             ELSEIF opr0.index = 6 THEN '如果是左括号
     
177.                 CALL PushOpr(oprStk, opr0) '将左括号无条件进栈
     
178.             ELSEIF opr0.index = 7 THEN '如果是右括号
     
179.                 CALL PeekOpr(oprStk, opr) '看符栈栈顶
     
180.                 WHILE opr.level <> -1 AND oprStk.top > 0 '一直循环直到遇到左括号,或者栈空
     
181.                     CALL PopOpr(oprStk, opr) '出栈一个运算符
     
182.                     tmpXp = tmpXp & " " & TRIM$(opr.opname) & " " '存入逆波兰式
     
183.                     CALL PeekOpr(oprStk, opr) '继续看符栈栈顶
     
184.                 WEND
     
185.                 CALL PopOpr(oprStk, opr) '将左括号出栈并抛弃
     
186.             ELSE
     
187.                 ERRNUM = 3 '非法字符
     
188.                 EXIT SUB   '退出子程式
     
189.             END IF
     
190.             tmpEle = "" '将临时元素清空
     
191.             p = " " '将逆波兰式元素间隔符设为一个空格
     
192.         ELSE
     
193.             ERRNUM = 3 '非法字符
     
194.             EXIT SUB   '结束子程序运行
     
195.         END IF
     
196.     NEXT
     
197.     WHILE oprStk.top > 0 '一直循环直到栈空
     
198.         CALL PeekOpr(oprStk, opr0) '看栈顶
     
199.         IF opr0.level = -1 THEN '还有剩余左括号未出栈
     
200.             ERRNUM = 4 '括号不匹配报错
     
201.             EXIT LOOP  '退出循环
     
202.         END IF
     
203.         CALL PopOpr(oprStk, opr) '将运算符出栈
     
204.         tmpXp = tmpXp & " " & TRIM$(opr.opname) & " " '存入逆波兰式
     
205.     WEND
     
206.     xp = TRIM$(tmpXp) '去掉逆波兰式两侧空格
     
207.     REPLACE "  " WITH " " IN xp '将逆波兰式中连续两个空格替换为一个空格
     
208. END SUB
     
209. 
     
210. FUNCTION IsNumeric(BYVAL str AS STRING) AS INTEGER '判断字符串是否是数字类型
     
211.     LOCAL i AS INTEGER
     
212.     LOCAL c AS INTEGER
     
213.     FUNCTION = 1
     
214.     FOR i = 1 TO LEN(str)
     
215.         c = ASC(MID$(str, i, 1))
     
216.         IF NOT ((c >= 48 AND c <= 57) OR c = 46 OR c = 45) THEN
     
217.             FUNCTION = 0 '所检测字符串中有一个不是合法的字符该字符串就不是数字类型
     
218.             EXIT FUNCTION
     
219.         END IF
     
220.     NEXT
     
221. END FUNCTION
     
222. 
     
223. FUNCTION Calculate(BYVAL expr AS STRING) AS DOUBLE '计算已经格式化的逆波兰式得到答案
     
224.     LOCAL oprStk AS OPRSTACK '定义符栈
     
225.     LOCAL numStk AS NUMSTACK '定义数栈
     
226.     LOCAL opr    AS OPRTYPE  '临时运算符
     
227.     LOCAL tmpEle AS STRING   '临时元素
     
228.     LOCAL ts     AS STRING   '临时字符串
     
229.     LOCAL i AS INTEGER       '计数器
     
230.     LOCAL z AS INTEGER       '临时整型变量
     
231.     LOCAL x AS DOUBLE        '第一个操作数
     
232.     LOCAL y AS DOUBLE        '第二个操作数
     
233.     LOCAL a AS DOUBLE        '运算结果数
     
234.     LOCAL b AS INTEGER '数字输入完毕 标记
     
235.     LOCAL d AS INTEGER '上一个为数字 标记
     
236. 
     
237.     CALL InitOprTable()       '初始化运算符表
     
238.     CALL InitOprStack(oprStk) '初始化符栈
     
239.     CALL InitNumStack(numStk) '初始化数栈
     
240.     expr = expr & " " '将逆波兰式表达式末尾加上一个空格作为结束标记
     
241. 
     
242.     FOR i = 1 TO LEN(expr) '从表达式开始扫描至结束
     
243.         ScanIdx = i '设置扫描索引
     
244.         ts = MID$(expr, i, 1) '临时字符串为表达式中间一个字符
     
245.         IF ts <> " " THEN '若这个字符不是空格
     
246.             tmpEle = tmpEle & ts '临时表达式元素累积
     
247.             IF IsOper(oprStk, tmpEle, z, opr) = 0 AND IsNumeric(tmpEle) = 1 THEN '若该元素不是运算符并且是数字
     
248.                 d = 1 '上一个字符为数字的标记为真
     
249.             ELSEIF IsOper(oprStk, tmpEle, z, opr) > 0 THEN '若该元素是运算符
     
250.                 CALL PopNum(numStk, x) '出栈一个操作数
     
251.                 CALL PopNum(numStk, y) '出栈另一个操作数
     
252.                 CALL PushNum(numStk, HandelOpr(y, x, IsOper(oprStk, tmpEle, z, opr))) '将操作数进行运算得到答案
     
253.                 d = 0 '数字标记为假
     
254.             ELSE '其他情况
     
255.                 ERRNUM = 3 '触发非法字符错误
     
256.                 EXIT FUNCTION '退出函数
     
257.             END IF
     
258.         ELSE '如果当前字符是空格
     
259.             IF d = 1 THEN CALL PushNum(numStk, CDBL(VAL(tmpEle))) '如果数字标记为真,将数字压入数栈
     
260.             b = 1: tmpEle = "" '数字输入完毕,标记为真.清空临时元素
     
261.         END IF
     
262.     NEXT
     
263.     CALL PopNum(numStk, a) '将最后一个数字弹出数栈
     
264.     FUNCTION = a '将该数字设为函数返回值
     
265. END FUNCTION '函数封闭
     
266. '===========代码结束===========
     

复制代码

main.bas

1. #COMPILE EXE "XT.EXE"
   
2. #DIM ALL
   
3. #INCLUDE ONCE "header.bi"
   
4. 
   
5. FUNCTION PBMAIN () AS LONG
   
6.     DIM xp AS STRING
   
7.     DIM r  AS STRING
   
8.     DIM t  AS STRING
   
9.     xp = "?"
   
10.     DO
    
11.         ERRNUM = 0
    
12.         xp = INPUTBOX$("PLEASE INPUT A" & $LF & "  EXPRESSION" & $LF & t, "WCMC-XT", xp)
    
13.         r = xp
    
14.         IF LEFT$(xp, 1) = "@" THEN
    
15.             xp = MID$(xp, 2)
    
16.             CALL Compute(xp)
    
17.             xp = TRIM$(STR$(Calculate(xp)))
    
18.         ELSEIF LEFT$(xp, 1) = "#" THEN
    
19.             xp = MID$(xp, 2)
    
20.             xp = TRIM$(STR$(Calculate(xp)))
    
21.         ELSEIF LEFT$(xp, 1) = "?" THEN
    
22.             MSGBOX "(C) 2015 CYYCOISH" & $LF & "   201502130730" & _
    
23.                    $LF & "    @[Infix]" & $LF & "    #[Suffix]", , "WCMC-XT"
    
24.         ELSE
    
25.             CALL Compute(xp)
    
26.         END IF
    
27.         SELECT CASE ERRNUM
    
28.         CASE 0
    
29.             t = ""
    
30.         CASE 1
    
31.             t = "Error 101 At " & STR$(ScanIdx) & " :Overflow."
    
32.         CASE 2
    
33.             t = "Error 102 At " & STR$(ScanIdx) & " :Missing Operator."
    
34.         CASE 3
    
35.             t = "Error 103 At " & STR$(ScanIdx) & " :Illegal Character."
    
36.         CASE 4
    
37.             t = "Error 104 At " & STR$(ScanIdx) & " :Missing Brackets."
    
38.         CASE 5
    
39.             t = "Error 105 At " & STR$(ScanIdx) & " :Missing Number."
    
40.         END SELECT
    
41.         IF xp = "" THEN xp = r
    
42.     LOOP UNTIL r = ""
    
43.     FUNCTION = 0
    
44. END FUNCTION
    

复制代码

具体实现有详尽的代码注释，大家可以在此贴讨论该算法
这里将代码与程序资源打包发布在这里，请各位踊跃讨论不要潜水：

游客，如果您要查看本帖隐藏内容请回复

cyycoish

@元始天尊
没用C++等，用的是BASIC语言但
不知道您对这个算法有没有兴趣
{:soso_e100:}

cyycoish

{:soso_e130:}熬了一宿来调试程序
这里必须感谢站长@0xAA55
是他给了我很大的鼓励
{:soso_e181:}

元始天尊

cyycoish 发表于 2015-2-13 11:22
@元始天尊
没用C++等，用的是BASIC语言但
不知道您对这个算法有没有兴趣

不得不说，1年前研究过，现在都不太会了^_^，另外不要称“您”，吓着我了^_^。。。。我记着你不是写过一个比较完整的吗，那个就挺好的
这个图好像没有提出什么新算法

搬砖工

看看原理来

tlwh163

看看原理来