読者です 読者をやめる 読者になる 読者になる

ichirin2501's diary

いっちりーん。

SPOJ :: 4. Transform the Expression

/spoj

SPOJ.com - Problem ONP
問題概要
与えられる数式を逆ポーランド記法に直して出力
問題文には明示されてないけど、与えられる数式文法はたぶんこんな感じ

<expression> ::= (<formula>)
<formula> ::= <factor>+<factor> |
              <factor>-<factor> |
              <factor>*<factor> |
              <factor>/<factor> |
              <factor>^<factor>
<factor> ::= <alfabet> | <expression>
<alfabet> ::= a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z

やるだけ?

#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys

def ReversePolishNotation(line):
    buf = []
    ret = []
    for c in line:
        if 'a'<=c<='z' :
            ret.append(c)
        elif c==')':
            while buf:
                t = buf.pop()
                if t=='(':
                    break
                ret.append(t)
        else:
            buf.append(c)
        
    return "".join(ret)

def main():

    n = int(sys.stdin.readline())
    for i in range(n):
        line = sys.stdin.readline().strip()
        print ReversePolishNotation(line)
            
if __name__ == '__main__' :
    main()
sample input
6
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))
(a+b)
(((a-b)*c))
((a^b))

sample output
abc*+
ab+zx+*
at+bac++cd+^*
ab+
ab-c*
ab^