前缀、中缀、后缀表达式相互转换

2014/11/4 posted in  算法&数据结构

这里只提供了使用栈的方法,还可以利用树的遍历实现。

中缀表达式转换为前缀表达式。 

首先创建算术符栈OPTR和表达式栈RESULT并置空,然后依次逆序检查中缀表达式每个字符,不同字符按不同情况处理:

(1).若是空格直接跳过。

(2).若是操作数直接压入RESULT栈。

(3).若是‘)’直接存入OPTR栈,等待和它匹配的‘(’出现。

(4).若是‘(’表明括号中的终追表达式已转换完毕,则循环弹出OPTR栈的操作符,  并压入RESULT栈,直到取出一个和它匹配的‘)’为止,‘)’出栈丢弃。

(5).若是运算符,如果OPTR栈是空的或者该运算符优先级高于或等于OPTR栈的栈顶运算符则入栈,如果该运算符优先级低,则循环弹出OPTR栈的运算符并存入RESULT,直到遇到栈顶的运算符优先级等于或小于该算法或栈空为止,然后将当前操作符存入OPTR栈。

若表达式扫描完后OPTR栈还有运算符,则依次弹出压入RESULT栈,直至栈空。最后RESULT栈中的元素依次出栈存入字符串中,并向字符串中写入‘�’,则字符串中存放的就是前缀表达式。

 前缀表达式求值。 

首先建立一个栈并置空,然后从右到左扫描前缀表达式,从右边第一个字符开始判断,如果当前字符是数字则一直到数字串的末尾再将整个数字串作为一个整体压人栈,如果是运算符,则将栈顶和次栈顶的两个“数字串”出栈并作相应的运算,然后将计算结果入栈。扫描完前缀式后,栈中剩余的最后一个值就是前缀表达式的值。

中缀表达式转换成后缀表达式。

首先创建栈并置空,然后依次检查中缀表达式每个字符,不同字符按不同情况处理:

(1).若是操作数,就直接将存入字符串exp[]中。

(2).若是‘(’则将其压入栈中。

(3).若是‘)’则依次弹栈并存入字符串exp[]中,直到遇到取出和它匹配的‘(’为止,‘(’出栈丢弃。

(4).若是操作符,如果栈空或者该操作符的优先级大于栈顶操作符则将其放入到栈中。如果该操作符的优先级小于等于栈顶操作符则弹出栈中的操作符存入字符串exp[]中,直到该操作符的优先级大于栈顶操作符或栈空,然后将该操作符入栈。

当读到了中缀式的末尾时,如果栈非空则将栈中所有元素依次弹出存入字符串exp[]中,最后见‘�’存入exp[]中,则exp[]中存储的就是后缀表达式。

后缀表达式求值。 

首先建立一个栈并置空,然后依次左扫描后缀表达式,从第一个字符开始判断,如果当前字符是数字则一直到数字串的末尾再将整个数字串作为一个整体压人栈,如果是运算符,则将栈顶和次栈顶的两个“数字串”出栈并作相应的运算,然后将计算结果入栈。扫描完前缀式后,栈中剩余的最后一个值就是前缀表达式的值。