【SPOJ】Transform the Expression

SPOJ Problem Set (classical)

4. Transform the Expression

Problem code: ONP

Transform the algebraic expression with brackets into RPN form (Reverse Polish Notation). Two-argument operators: +, -, *, /, ^ (priority from the lowest to the highest), brackets ( ). Operands: only letters: a,b,…,z. Assume that there is only one RPN form (no expressions like a*b*c).

Input

t [the number of expressions <= 100]
expression [length <= 400]
[other expressions]

Text grouped in [ ] does not appear in the input file.

Output

The expressions in RPN form, one per line.

Example

Input:
3
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))

Output:
abc*+
ab+zx+*
at+bac++cd+^*

———————–
贴代码啊贴代码~

#coding:utf-8
def main():
    expnum = input()
    explist = list()
    oplist = list(['+', '-', '*', '/', '^']) #priority: lowest to the highest
    for i in range(0, expnum):
        explist.append(raw_input())
    for exp in explist:
        opstack = list(['None'])
        ans = ''
        for ch in exp:
            if ch == '(':
                opstack.append(ch)
            elif ch == ')':
                while True:
                    top = opstack.pop()
                    if top == '(':
                        break
                    ans += top
            elif ch in oplist:
                top = opstack[-1]
                if top == 'None' or top == '(': #在这犯了个大错=。=
                    opstack.append(ch)
                elif oplist.index(ch) > oplist.index(top):
                    opstack.append(ch)
                else:
                    ans += opstack.pop()
                    opstack.append(ch)
            elif 'a' <= ch <= 'z':
                ans += ch
            else:
                print 'Get an unexpected character !'
                return
        while True:
            top = opstack.pop()
            if top == 'None':
                break
            ans += top
        print ans

if __name__ == '__main__':
    main()

“#在这犯了个大错”那里一开始写成:

if top == 'None' or '(':

这把我纠结的…这个不清楚语法不能自以为pythonic额…

逻辑很简单,逆波兰表达法栈实现:
1.遇到字母直接输出
2.遇到”(“入栈
3.遇到”)”出栈直到出来”(”
4.遇到操作符先和栈顶比较
a.栈顶是操作符,则优先级小的放栈顶输出,把这个推进去,优先级大的直接输出
b.栈顶是”None”(栈底标识)或括号就直接入栈
5.最后玩完了清空栈直到”None”

Tags : ,

0 thoughts on “【SPOJ】Transform the Expression”

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Click the right image To submit your comment: