中缀表达式转后缀

题目描述:

将输入的中缀表达式转成后缀表达式输出。

注意：输入数据保证数字都为正整数，可能有0。

输入格式:

输入一行表示中缀表达式。

输出格式:

输出对应的后缀表达式，运算数、运算符之前均以一个空格分开。

数据范围:

中缀表达式中的字符在100之内。

样例输入:

1+(3+2)*(7^2+6*9)/(2)

样例输出:

1 3 2 + 7 2 ^ 6 9 * + * 2 / +

提示:

中缀表达式转后缀表达式，具体规则如下：

（1）遇到数直接输出，不进栈；

（2）遇到运算符或括号：

       1） 左括号，直接进栈；

       2）右括号，把栈中的运算符依次出栈，直到碰到第一个左括号为止；

       3）运算符，把栈中优先级别大于等于它的运算符依次出栈，直到左括号或栈底。

 

请完善以下程序：

gs = input()
st1 = []
st2 = []
js = ""
dic={ "^":3, "*":2, "/":2, "+":1, "-":1 }
for i in range(len(gs)):
    if "0" <= gs[i] <= "9":
        _______________ #填空1
    else:
        if len( js ) > 0:
            st1.append( js )
            js = ""
        if gs[i] == ")":
            while  st2[ -1 ] != "(":
                ____________________ #填空2
            st2.pop()
        elif gs[ i ] == "(":
            __________________  #填空3
        elif gs[ i ] in  [ "*", "+", "-", "^", "/" ] :
            while _________________________________________: #条件易错 填空4
                st1.append( st2.pop() )
            st2.append( gs[i] )  #易错
if ___________________: #这个条件易忽略  填空5
    st1.append( js )
while len( st2 ) != 0:
    st1.append( st2.pop() )
print( " ".join( st1 ) )

时间限制: 1000ms
空间限制: 256MB

---

来源: 原创