SPOJ :: 4. Transform the Expression
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^