Pythonで逆ポーランド記法の計算

後輩が楽しそうに解いてたので便乗して解いてみました
入力なんかの想定はAOJのコレ

素直に解く

まずはCやJavaなんかで解く時と同じような要領で
演算を辞書に押し込んでしまえば条件分岐が減ってすっきりします

ops = {"+": lambda a, b: b + a,
       "-": lambda a, b: b - a,
       "*": lambda a, b: b * a}
stack = []
for s in raw_input().split():
    if s in ops:
        stack.append(ops[s](stack.pop(), stack.pop()))
    else:
        stack.append(int(s))
print stack[-1]

listを継承して解く

要素を入れたら勝手に合成してくれるstackを作ってみました
あんまり上手な書き方ではないかもしれません

class RPN(list):
    ops = {"+": lambda a, b: b + a,
           "-": lambda a, b: b - a,
           "*": lambda a, b: b * a}
    def __init__(self):
        list.__init__(self)
    def append(self, value):
        if value in self.ops:
            list.append(self, self.ops[value](self.pop(), self.pop()))
        else:
            list.append(self, int(value))

rpn = RPN()    
for s in raw_input().split():
    rpn.append(s)
print rpn[-1]

高階関数を使って解く

組み込み関数のreduceを使って解きます
stackをリレーするイメージ

ops = {"+": lambda a, b: b + a,
       "-": lambda a, b: b - a,
       "*": lambda a, b: b * a}
def calc(stack, s):
    if s in ops:
        stack.append(ops[s](stack.pop(), stack.pop()))
    else:
        stack.append(int(s))
    return stack
print reduce(calc, raw_input().split(), [])[-1]

一行で解く

先の解き方からの発展形
if-elseが面倒でついにevalを使ってしまいましたが、もちろん使わなくても解けます

print reduce(lambda stack, s: stack[:-2] + [eval("{} {} {}".format(stack[-2], s, stack[-1]))] if s in "+-*" else stack + [int(s)], raw_input().split(), [])[-1]

まとめ

一つの問題を解くにもアプローチの仕方は様々
ワンライナーを目指すと2度楽しい

SRM608 div2

250-概要
数直線上を[-A, B]の範囲で動けるロボットがいます。
右(R)か左(L)へ進むよう指示を出します。
初めロボットは0の点に配置されています。
指示が終わったとき、ロボットはどの点にいるでしょう。

解法・感想
minとmaxで範囲を超えないよう押さえ込みます。

ソースコード

from math import *
class OneDimensionalRobotEasy:
    def finalPosition(self, commands, A, B):
        cur = 0
        for c in commands:
            if c == "R":
                cur = min(B, cur + 1)
            elif c == "L":
                cur = max(-A, cur - 1)
        return cur 

600-概要
飴の入った箱が与えられます。
全ての箱の中身を合わせると飴の数はC個になります。
それぞれの箱には、その箱に入っている飴の数の上限が与えられています。
今X個の飴が必要です。
最低でいくつの箱を取り出せば良いでしょう。

解法・感想
(最低限得られる飴の数) = max(0, C - (開けていない箱の上限の和))
あとは上限の大きな箱から開けていき最低限得られる飴の数がXを超えるまで回せば求まります。
tupleで与えられているのを忘れ.sort()を使っていたため弾かれてました。
プラグインに頼り切った結果です。残当。

ソースコード

class MysticAndCandiesEasy:
    def minBoxes(self, C, X, high):
        N = len(high)
        high = list(high)
        high.sort()
        su = [sum(high[:i]) for i in xrange(1, N + 1)]
        for i in xrange(N):
            if C - su[N - i - 1] >= X:
                return i
        return N

1000-概要
隣接行列が与えられます。
ある人が長さLの経路が何通りあるか調べたいそうです。
多項式時間で解けるでしょうか。

解法・感想
ある点を通る閉路（単純閉路？）が二つ以上存在すると指数時間必要になります。
これを求めるには始点（終点）を合流地点とするような二つの閉路の存在を確かめれば十分です。

ソースコード

class BigOEasy:
    def isBounded(self, graph):
        graph = [map(lambda x: x == "Y", g) for g in graph]
        N = len(graph)
        def check(start):
            q = set([start])
            visited = [False] * N
            flag = 0
            while len(q) != 0:
                cur = q.pop()
                for i in xrange(N):
                    if not graph[cur][i] or visited[i]:
                        continue
                    if i == start:
                        flag += 1
                        if flag > 1:
                            return True
                    else:
                        visited[i] = True
                        q.add(i)
            return False
        for i in xrange(N):
            if check(i):
                return "Unbounded"
        return "Bounded"