GoACM之逆波兰表达式

收藏到CSDN网摘


逆波兰表达式(Reverse Polish Notation)转换:
逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法），是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式，在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。因此逆波兰记法广泛地被用于计算器。
SPOJ的ONP问题正是逆波兰表达式的生成问题.

这个问题可以用火车调度场算法解决,Shunting yard算法是一个用于将中缀表达式转换为后缀表达式的经典算法，由艾兹格·迪杰斯特拉引入，因其操作类似于火车编组场而得名。非常巧妙.具体可参考这里.

下面是AC的代码,py2.7

import string
def rpnGenerate(s):
    pri = {'+':0,'-':0,'*':1,'/':1,'^':2,'!':3}
    pat = {'+':'left','-':'left','*':'left','/':'left','^':'right','!':'right'}
    rpn = '' # result rpn string
    stack = [] # operator stack
    for c in s:
        if c==' ':
            continue
##        # output the current char, rpn and op stack
##        print '%s %10s %10s' % (c,rpn,stack)
        if c in string.digits+string.ascii_letters: # num
            rpn += c
        elif c=='(': # (
            stack.insert(0,c)
        elif c==')': # )
            if '(' not in stack: # error, no ( in stack
                break
            n = stack.pop(0) # pop operator until ( is the stack top
            while n!='(':
                rpn += n
                n = stack.pop(0)
        else: # operators
            if len(stack)==0:
                stack = [c]
                continue
            # pop a op if:
            # 1. stack top is not ( or )
            # 2. current op is left combine and priority is small than or equal to op on stack top
            # 3. current op is right combine and priority is small than op on stack top
            elif (stack[0] not in '()') and ((pat[c]=='left' and pri[c]<=pri[stack[0]]) or (pat[c]=='right' and pri[c]<pri[stack[0]])):
                rpn += stack.pop(0)
            # push op in stack
            stack.insert(0,c)
            
    if len(stack)>0: # stack is not empty
        if stack[0] in '()': # has ( or ), quotations don't match
            return 'error'
        else: # pop up all ops and return rpn
            rpn += ''.join(stack)
            return rpn
    else: # empty stack, return rpn
        return rpn
        
n = int(raw_input())
i = 0
while i<n:
    s = raw_input()
    print rpnGenerate(s)
    i += 1