找回密码
 立即注册→加入我们

QQ登录

只需一步,快速开始

搜索
热搜: 下载 VB C 实现 编写
查看: 7604|回复: 4

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

[复制链接]

85

主题

175

回帖

3990

积分

用户组: 超级版主

No. 418

UID
418
精华
14
威望
53 点
宅币
1974 个
贡献
1582 次
宅之契约
0 份
在线时间
252 小时
注册时间
2014-8-9
发表于 2015-2-13 11:07:09 | 显示全部楼层 |阅读模式

欢迎访问技术宅的结界,请注册或者登录吧。

您需要 登录 才可以下载或查看,没有账号?立即注册→加入我们

×
本帖最后由 cyycoish 于 2015-2-13 11:10 编辑

最近在研究表达式的处理,顺手写了这么一款小程序。
为了实现表达式计算,本程序使用了两个步骤:1.中缀转后缀 2.计算后缀表达式(逆波兰式)
表达式支持 + - * / \ ^ 共6中运算符分别为 加、减、乘、除、模、幂。均是标准的双目运算符。
输入一个中缀表达式,形如 “1+1”程序可以自动转换为相应后缀表达式“1 1 +”
在中缀表达式之前加“@”符号,可以计算该中缀表达式。在逆波兰式之前加“#”可以计算逆波兰
式的值。支持小数,负数,括号。{} 花括号 [] 方括号 () 圆括号 可以混搭。
程序可以识别 括号不匹配 非法字符 缺少运算符 缺少操作数 4 种错误。
下面上图:
a0.JPG a1.JPG a2.JPG a3.JPG
a4.JPG a5.JPG a6.JPG a7.JPG
原理如下:
k1.JPG k2.JPG
该程序由powerbasic10 编译而成 源代码:
header.bi
  1. MACRO CONST = MACRO
  2. CONST N = 100 '数栈大小
  3. CONST M = 100 '符栈大小
  4. CONST O = 6   '运算符个数

  5. GLOBAL ERRNUM   AS INTEGER '错误标识符
  6. GLOBAL ScanIdx  AS LONG    '扫描索引

  7. TYPE OPRTYPE              '运算符
  8.     opname AS STRING * 10 '运算符字符串表示
  9.     level  AS INTEGER     '运算符优先级
  10.     index  AS INTEGER     '运算符标识
  11. END TYPE

  12. TYPE NUMSTACK           '数栈定义
  13.     stack(N) AS DOUBLE  '数栈栈体
  14.     top      AS INTEGER '数栈栈顶
  15. END TYPE

  16. TYPE OPRSTACK           '符栈定义
  17.     stack(M) AS OPRTYPE '符栈栈体
  18.     top      AS INTEGER '符栈栈顶
  19. END TYPE

  20. GLOBAL Oper() AS OPRTYPE '运算符表

  21. SUB InitNumStack(BYREF numStk AS NUMSTACK) '数栈初始化
  22.     numStk.top = 0 '栈顶为0栈为空
  23. END SUB

  24. SUB PushNum(BYREF numStk AS NUMSTACK, BYVAL v AS DOUBLE) '数栈压栈
  25.     IF numStk.top = N - 1 THEN '若数栈达到存贮上限
  26.         ERRNUM = 1 '溢出报错
  27.     ELSE
  28.         numStk.top = numStk.top + 1 '向上堆
  29.         numStk.stack(numStk.top) = v '数字进栈
  30.     END IF
  31. END SUB

  32. SUB PopNum(BYREF numStk AS NUMSTACK, BYREF v AS DOUBLE) '数栈出栈
  33.     IF numStk.top = 0 THEN '若栈空
  34.         ERRNUM = 5 '数栈触底报错
  35.     ELSE
  36.         v = numStk.stack(numStk.top) '数字出栈
  37.         numStk.top = numStk.top - 1 '向下落
  38.     END IF
  39. END SUB

  40. SUB InitOprStack(BYREF oprStk AS OPRSTACK) '符栈初始化
  41.     oprStk.top = 0 '设栈空
  42. END SUB

  43. SUB PushOpr(BYREF oprStk AS OPRSTACK, BYVAL sign AS OPRTYPE) '符栈压栈
  44.     IF oprStk.top = M THEN '达到上限
  45.         ERRNUM = 1 '符栈溢出
  46.     ELSE
  47.         oprStk.stack(oprStk.top) = sign '操作符进栈
  48.         oprStk.top = oprStk.top + 1 '向上堆
  49.     END IF
  50. END SUB

  51. SUB PopOpr(BYREF oprStk AS OPRSTACK, BYREF rtn AS OPRTYPE) '符栈出栈
  52.     IF oprStk.top = 0 THEN
  53.         ERRNUM = 2 '符栈触底
  54.     ELSE
  55.         oprStk.top = oprStk.top - 1 '符栈向下落
  56.         rtn.opname = TRIM$(oprStk.stack(oprStk.top).opname) '出栈
  57.         rtn.level = oprStk.stack(oprStk.top).level
  58.         rtn.index = oprStk.stack(oprStk.top).index
  59.     END IF
  60. END SUB

  61. SUB PeekOpr(BYVAL oprStk AS OPRSTACK, BYREF rtn AS OPRTYPE) '看符栈栈顶
  62.     IF oprStk.top > 0 THEN '若符栈不为空
  63.         rtn.opname = TRIM$(oprStk.stack(oprStk.top - 1).opname) '传递栈顶运算符参数
  64.         rtn.level = oprStk.stack(oprStk.top - 1).level
  65.         rtn.index = oprStk.stack(oprStk.top - 1).index
  66.     END IF
  67. END SUB

  68. SUB InitOprTable() '初始化运算符表
  69.     DIM Oper(O) AS GLOBAL OPRTYPE '初始化运算符表载体数组
  70.     Oper(0).opname = "+": Oper(0).level =  1: Oper(0).index = 1
  71.     Oper(1).opname = "*": Oper(1).level =  2: Oper(1).index = 2
  72.     Oper(2).opname = "/": Oper(2).level =  2: Oper(2).index = 3
  73.     Oper(3).opname = "": Oper(3).level =  2: Oper(3).index = 4
  74.     Oper(4).opname = "^": Oper(4).level =  3: Oper(4).index = 5
  75.     Oper(5).opname = "(": Oper(5).level = -1: Oper(5).index = 6
  76.     Oper(6).opname = ")": Oper(6).level = -1: Oper(6).index = 7
  77.     '运算符名称           运算符优先级        运算符索引标识
  78. END SUB

  79. FUNCTION HandelOpr(BYVAL a AS DOUBLE, BYVAL b AS DOUBLE, BYVAL index AS INTEGER) AS DOUBLE '定义运算符运算过程
  80.     LOCAL ans AS DOUBLE '定义运算结果
  81.     SELECT CASE index '按索引区分运算符
  82.     CASE 1 '加法运算
  83.         ans = a + b
  84.     CASE 2 '乘法运算
  85.         ans = a * b
  86.     CASE 3 '除法运算
  87.         ans = a / b
  88.     CASE 4 '取模运算
  89.         ans = a MOD b
  90.     CASE 5 '幂运算
  91.         ans = a ^ b
  92.     END SELECT
  93.     FUNCTION = ans '函数返回值
  94. END FUNCTION

  95. FUNCTION IsOper(BYREF oprStk AS OPRSTACK, BYVAL s AS STRING, BYREF level AS INTEGER, _
  96.                 BYREF ioper AS OPRTYPE) AS INTEGER '判定是否为运算符函数
  97.     LOCAL i AS INTEGER
  98.     FUNCTION = 0
  99.     FOR i = 0 TO O '遍历运算符表
  100.         IF s = TRIM$(oper(i).opname) THEN '找到相似运算符
  101.             level = oper(i).level '传递运算符优先级
  102.             ioper = oper(i) '传递运算符本身
  103.             FUNCTION = oper(i).index '返回运算符索引标识
  104.             EXIT FUNCTION '退出函数
  105.         END IF
  106.     NEXT
  107. END FUNCTION

  108. FUNCTION PreProcessor(BYVAL str AS STRING) AS STRING '预处理器
  109.     str = TRIM$(str) '去入口字符串两端空格
  110.     REPLACE "-" WITH "+-" IN str '将减去一个数变为加上一个数的相反数
  111.     REPLACE ANY "{[" WITH "((" IN str '将左括号统一
  112.     REPLACE ANY "}]" WITH "))" IN str '统一右侧括号
  113.     IF LEFT$(str, 2) = "+-" THEN str = MID$(str, 2) '如果表达式第一个数为负数,消除替换符号后的副作用
  114.     FUNCTION = str '返回处理完毕后的字符串
  115. END FUNCTION

  116. SUB Compute(BYREF xp AS STRING) '将源表达式转为逆波兰式
  117.     LOCAL oprStk AS OPRSTACK '定义符栈
  118.     LOCAL opr0   AS OPRTYPE  '定义临时操作符1
  119.     LOCAL opr    AS OPRTYPE  '定义临时操作符2
  120.     LOCAL tmpEle AS STRING   '临时表达式元素
  121.     LOCAL tmpXp  AS STRING   '临时表达式
  122.     LOCAL i  AS INTEGER      '计数器
  123.     LOCAL j  AS INTEGER      '计数器
  124.     LOCAL nb AS INTEGER      '为数字时该值为1,否则为0
  125.     LOCAL l  AS INTEGER      '临时存放优先级
  126.     LOCAL p  AS STRING       '临时存放空格

  127.     ScanIdx = 0               '初始扫描索引
  128.     CALL InitOprTable()       '初始化运算符表
  129.     CALL InitOprStack(oprStk) '初始化符栈

  130.     xp = PreProcessor(xp)     '预处理表达式字符串

  131.     FOR i = 1 TO LEN(xp) '从预处理后的表达式开始到结束
  132.         ScanIdx = i: tmpEle = "" '设置扫描索引,临时元素设空
  133.         tmpEle = TRIM$(tmpEle & MID$(xp, i, 1))
  134.         nb = 1 '数字标记为真
  135.         IF IsOper(oprStk, tmpEle, l, opr0) = 0 THEN '若不是运算符
  136.             FOR j = 1 TO LEN(tmpEle) '逐个扫描元素
  137.                 LOCAL char AS INTEGER
  138.                 char = ASC(MID$(tmpEle, j, 1)) '记录元素内各个字符的asc码
  139.                 IF (char >= 48 AND char <= 57) OR char = 46 OR char = 45 THEN '如果是数字,小数点,负号
  140.                     nb = 1 '数字标记为真
  141.                 ELSE '否则
  142.                     nb = 0 '数字标记为假
  143.                     EXIT FOR '不是数字立即退出循环
  144.                 END IF
  145.             NEXT
  146.             IF nb = 1 THEN tmpXp = tmpXp & p & tmpEle: p = "" '将数字存入临时逆波兰式
  147.         ELSEIF IsOper(oprStk, tmpEle, l, opr0) >= 1 AND nb = 1 THEN '如果前一个为数字,当前为运算符
  148.             IF opr0.index <> 6 AND opr0.index <> 7 THEN '如果不是括号
  149.                 CALL PeekOpr(oprStk, opr) '看符栈栈顶
  150.                 WHILE opr.level >= opr0.level AND oprStk.top > 0 '当当前运算符优先级大于等于栈顶优先级并且符栈不为空
  151.                     CALL PopOpr(oprStk, opr) '出栈一个运算符
  152.                     tmpXp = tmpXp & " " & TRIM$(opr.opname) & " " '将运算符存入逆波兰式
  153.                     CALL PeekOpr(oprStk, opr) '再看符栈栈顶
  154.                 WEND
  155.                 CALL PushOpr(oprStk, opr0) '将当前运算符压入符栈
  156.             ELSEIF opr0.index = 6 THEN '如果是左括号
  157.                 CALL PushOpr(oprStk, opr0) '将左括号无条件进栈
  158.             ELSEIF opr0.index = 7 THEN '如果是右括号
  159.                 CALL PeekOpr(oprStk, opr) '看符栈栈顶
  160.                 WHILE opr.level <> -1 AND oprStk.top > 0 '一直循环直到遇到左括号,或者栈空
  161.                     CALL PopOpr(oprStk, opr) '出栈一个运算符
  162.                     tmpXp = tmpXp & " " & TRIM$(opr.opname) & " " '存入逆波兰式
  163.                     CALL PeekOpr(oprStk, opr) '继续看符栈栈顶
  164.                 WEND
  165.                 CALL PopOpr(oprStk, opr) '将左括号出栈并抛弃
  166.             ELSE
  167.                 ERRNUM = 3 '非法字符
  168.                 EXIT SUB   '退出子程式
  169.             END IF
  170.             tmpEle = "" '将临时元素清空
  171.             p = " " '将逆波兰式元素间隔符设为一个空格
  172.         ELSE
  173.             ERRNUM = 3 '非法字符
  174.             EXIT SUB   '结束子程序运行
  175.         END IF
  176.     NEXT
  177.     WHILE oprStk.top > 0 '一直循环直到栈空
  178.         CALL PeekOpr(oprStk, opr0) '看栈顶
  179.         IF opr0.level = -1 THEN '还有剩余左括号未出栈
  180.             ERRNUM = 4 '括号不匹配报错
  181.             EXIT LOOP  '退出循环
  182.         END IF
  183.         CALL PopOpr(oprStk, opr) '将运算符出栈
  184.         tmpXp = tmpXp & " " & TRIM$(opr.opname) & " " '存入逆波兰式
  185.     WEND
  186.     xp = TRIM$(tmpXp) '去掉逆波兰式两侧空格
  187.     REPLACE "  " WITH " " IN xp '将逆波兰式中连续两个空格替换为一个空格
  188. END SUB

  189. FUNCTION IsNumeric(BYVAL str AS STRING) AS INTEGER '判断字符串是否是数字类型
  190.     LOCAL i AS INTEGER
  191.     LOCAL c AS INTEGER
  192.     FUNCTION = 1
  193.     FOR i = 1 TO LEN(str)
  194.         c = ASC(MID$(str, i, 1))
  195.         IF NOT ((c >= 48 AND c <= 57) OR c = 46 OR c = 45) THEN
  196.             FUNCTION = 0 '所检测字符串中有一个不是合法的字符该字符串就不是数字类型
  197.             EXIT FUNCTION
  198.         END IF
  199.     NEXT
  200. END FUNCTION

  201. FUNCTION Calculate(BYVAL expr AS STRING) AS DOUBLE '计算已经格式化的逆波兰式得到答案
  202.     LOCAL oprStk AS OPRSTACK '定义符栈
  203.     LOCAL numStk AS NUMSTACK '定义数栈
  204.     LOCAL opr    AS OPRTYPE  '临时运算符
  205.     LOCAL tmpEle AS STRING   '临时元素
  206.     LOCAL ts     AS STRING   '临时字符串
  207.     LOCAL i AS INTEGER       '计数器
  208.     LOCAL z AS INTEGER       '临时整型变量
  209.     LOCAL x AS DOUBLE        '第一个操作数
  210.     LOCAL y AS DOUBLE        '第二个操作数
  211.     LOCAL a AS DOUBLE        '运算结果数
  212.     LOCAL b AS INTEGER '数字输入完毕 标记
  213.     LOCAL d AS INTEGER '上一个为数字 标记

  214.     CALL InitOprTable()       '初始化运算符表
  215.     CALL InitOprStack(oprStk) '初始化符栈
  216.     CALL InitNumStack(numStk) '初始化数栈
  217.     expr = expr & " " '将逆波兰式表达式末尾加上一个空格作为结束标记

  218.     FOR i = 1 TO LEN(expr) '从表达式开始扫描至结束
  219.         ScanIdx = i '设置扫描索引
  220.         ts = MID$(expr, i, 1) '临时字符串为表达式中间一个字符
  221.         IF ts <> " " THEN '若这个字符不是空格
  222.             tmpEle = tmpEle & ts '临时表达式元素累积
  223.             IF IsOper(oprStk, tmpEle, z, opr) = 0 AND IsNumeric(tmpEle) = 1 THEN '若该元素不是运算符并且是数字
  224.                 d = 1 '上一个字符为数字的标记为真
  225.             ELSEIF IsOper(oprStk, tmpEle, z, opr) > 0 THEN '若该元素是运算符
  226.                 CALL PopNum(numStk, x) '出栈一个操作数
  227.                 CALL PopNum(numStk, y) '出栈另一个操作数
  228.                 CALL PushNum(numStk, HandelOpr(y, x, IsOper(oprStk, tmpEle, z, opr))) '将操作数进行运算得到答案
  229.                 d = 0 '数字标记为假
  230.             ELSE '其他情况
  231.                 ERRNUM = 3 '触发非法字符错误
  232.                 EXIT FUNCTION '退出函数
  233.             END IF
  234.         ELSE '如果当前字符是空格
  235.             IF d = 1 THEN CALL PushNum(numStk, CDBL(VAL(tmpEle))) '如果数字标记为真,将数字压入数栈
  236.             b = 1: tmpEle = "" '数字输入完毕,标记为真.清空临时元素
  237.         END IF
  238.     NEXT
  239.     CALL PopNum(numStk, a) '将最后一个数字弹出数栈
  240.     FUNCTION = a '将该数字设为函数返回值
  241. END FUNCTION '函数封闭
  242. '===========代码结束===========
复制代码

main.bas
  1. #COMPILE EXE "XT.EXE"
  2. #DIM ALL
  3. #INCLUDE ONCE "header.bi"

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

具体实现有详尽的代码注释,大家可以在此贴讨论该算法
这里将代码与程序资源打包发布在这里,请各位踊跃讨论不要潜水:
游客,如果您要查看本帖隐藏内容请回复


In the beginning I was not the best.
And the world was also not the best.
But I still know that I am who I am.
Because I think that it is good.
I have been working hard.
I have been keeping growth with the world.
And it was so.
回复

使用道具 举报

85

主题

175

回帖

3990

积分

用户组: 超级版主

No. 418

UID
418
精华
14
威望
53 点
宅币
1974 个
贡献
1582 次
宅之契约
0 份
在线时间
252 小时
注册时间
2014-8-9
 楼主| 发表于 2015-2-13 11:22:09 | 显示全部楼层
@元始天尊
没用C++等,用的是BASIC语言但
不知道您对这个算法有没有兴趣
{:soso_e100:}
In the beginning I was not the best.
And the world was also not the best.
But I still know that I am who I am.
Because I think that it is good.
I have been working hard.
I have been keeping growth with the world.
And it was so.
回复 赞! 靠!

使用道具 举报

85

主题

175

回帖

3990

积分

用户组: 超级版主

No. 418

UID
418
精华
14
威望
53 点
宅币
1974 个
贡献
1582 次
宅之契约
0 份
在线时间
252 小时
注册时间
2014-8-9
 楼主| 发表于 2015-2-13 11:25:49 | 显示全部楼层
{:soso_e130:}熬了一宿来调试程序
这里必须感谢站长@0xAA55
是他给了我很大的鼓励
{:soso_e181:}
In the beginning I was not the best.
And the world was also not the best.
But I still know that I am who I am.
Because I think that it is good.
I have been working hard.
I have been keeping growth with the world.
And it was so.
回复 赞! 靠!

使用道具 举报

307

主题

228

回帖

7319

积分

用户组: 真·技术宅

UID
2
精华
76
威望
291 点
宅币
5569 个
贡献
253 次
宅之契约
0 份
在线时间
945 小时
注册时间
2014-1-25
发表于 2015-2-13 21:15:44 | 显示全部楼层
cyycoish 发表于 2015-2-13 11:22
@元始天尊
没用C++等,用的是BASIC语言但
不知道您对这个算法有没有兴趣

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

使用道具 举报

0

主题

41

回帖

89

积分

用户组: 小·技术宅

UID
1457
精华
0
威望
2 点
宅币
44 个
贡献
0 次
宅之契约
0 份
在线时间
8 小时
注册时间
2016-1-29
发表于 2017-2-16 17:18:21 | 显示全部楼层
看看原理来
回复 赞! 靠!

使用道具 举报

QQ|Archiver|小黑屋|技术宅的结界 ( 滇ICP备16008837号 )|网站地图

GMT+8, 2024-3-29 18:21 , Processed in 0.050441 second(s), 35 queries , Gzip On.

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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