一.需求分析
1.1 问题描述
编写完整程序,将中缀表达式翻译成后缀表达式。表达式由操作数 ( 变
量 ) 、操作 ( 运算符 ) 以及小括弧 “ ( ” 和 “ ) ” 组成,其中:(1)操作包
括算术运算、关系运算和逻辑运算三类;(2)操作数为单个字符或由字母和数字
任意多个字符构成;(3)能够识别出简单的错误,如括弧不匹配。
1.2 基本要求
输入:中缀表达式,80 个字符以内。
输出:运算结果
功能:将中缀表达式转化为后缀表达式
二.系统设计
根据题目要求,将中缀表达式转化为后缀表达式。问题的解决方案有两种,
分别是利用栈结构实现算数表达式的四则运算或者利用二叉树把中缀表达式转
化为前缀表达式,我选择栈结构与树结构相结合来实现算数表达式的转化。
算法思想:
①:运用栈和队列来将中缀转换为后缀,栈用来储存字符,队列用来存储后
缀表达式。
②:输入字符串 c,若是数字的话直接进入队列,若是符号,为‘*’‘/’
‘(’,则线检查栈中的栈顶元素,前提是栈不为空,若栈不为空的话,栈顶元素
为‘*’||‘/’,则先将栈中的元素入队,如果栈顶是‘+’‘-’这些优先级小的,
则直接将 c 入栈。
③:如果 c 是优先级为“+”“-”的字符,先看一下栈是否为空,接着判断栈
顶元素是否为“(”,若是,则继续将 c 进栈,否则的话,将栈中的元素全部出栈,
直到栈空。
④:若 c 为“)”则将栈中所有符号弹栈并进入队列。
⑤:若 c 为“#”,则结束,并将栈中的剩余的符号全部入队列。
⑥:打印队列中的,出队打印。