当前位置导航:炫浪网>>网络学院>>编程开发>>C++教程>>C++进阶与实例

数据结构辅导---栈和队列

3. 把中缀表达式转换为后缀表达式的算法
    设以’@’字符作为结束符的中缀算术表达式已经保存在s1字符串中,转换后得到的后缀算术表达式拟存于s2字符串中。由中缀表达式转换为后缀表达式的规则可知:转换前后,表达式中的数值项的次序不变,而运算符的次序发生了变化,由处在两个运算对象的中间变为处在两个运算对象的后面,同时去掉了所有的括号。为了使转换正确,必须设定一个运算符栈,并在栈底放入一个特殊算符,假定为’@’字符,让它具有最低的运算符优先级,假定为数值0,此栈用来保存扫描中缀表达式得到的暂不能放入后缀表达式中的运算符,待它的两个运算对象都放入到后缀表达式以后,再令其出栈并写入到后缀表达式中。
    把中缀表达式转换为后缀表达式算法的基本思路是从头到尾地扫描中缀表达式中的每个字符,对于不同类型的字符按不情况进行处理。若遇到的是空格则认为是分隔符,不需要进行处理;若遇到的是数字或小数点,则直接写入到s2中,并在每个数值的最后写入一个空格;若遇到的是左括号,则应把它压入到运算符栈中,待以它开始的括号内的表达式转换完毕后再出栈;若遇到的是右括号,则表明括号内的中缀表达式已经扫描完毕,把从栈底直到保存着的对应左括号之间的运算符依次退栈并写入s2串中;若遇到的是运算符,当该运算符的优先级大于栈顶运算符的优先级(加减运算符的优先级设定为1,乘除运算符的优先级设定为2,在栈中保存的特殊运算符’@’和’(’的优先级设定为0)时,表明该运算符的后一个运算对象还没有被扫描并放入到s2串中,应把它暂存于运算符栈中,待它的后一个运算对象从s1串中读出并写入到s2串中后,再另其出栈并写入s2串中;若遇到的运算符的优先级小于等于栈顶运算符的优先级,这表明栈顶运算符的两个运算对象已经被保存到s2串中,应将栈顶运算符退栈并写入到s2串中,对于新的栈顶运算符仍继续进行比较和处理,直到被处理的运算符的优先级大于栈顶运算符的优先级为止,然后另该运算符进栈即可。
按照以上过程扫描到中缀表达式结束符’@’时,把栈中剩余的运算符依次退栈并写入到后缀表达式中,再向s2写入表达式结束符’@’和字符串结束符’\0’,整个转换过程就处理完毕,在s2中就得到了转换成的后缀表达式。
    例如,设中缀算术表达式s1为:10+(18+9*3)/15-6@,使用的运算符栈用R表示,则转换过程如下:
    (1)开始时存放后缀表达式的字符串s2为空,R中压入有’@’算符,它具有最低的优先级0:
   

                    
@                    
  
(2)当扫描到s1中的左括号时,s2和R中的数据变化如下:
1 0                   
@ + (                  

    (3)当扫描到s1中的数值3时,s2和R中的数据变化为:
1 0   1 8  9  3            
@ + ( + *                

共2页 首页 上一页 1 2 下一页 尾页 跳转到
相关内容
赞助商链接