AOJ スタックの実装

Pythonでスタックを作ってみます。

■問題
Elementary data structures – Stack

■方針
Pythonのリスト(配列)オブジェクトのappend()メソッドとpop()メソッドを使えば、スタックをあっという間に作れますが、ここではスタックポインタを自分で管理することにします。

スタックを表すStackクラスというものを作りました。

import sys

class Stack:
    def __init__(self, max):
        self.max = max
        self.stack = list(range(max))
        self.top = 0

    def push(self, value):
        if self.top == self.max:
            raise IndexError('スタックオーバーフロー')

        self.stack[self.top] = value
        self.top += 1

    def pop(self):
        if self.top == 0:
            raise IndexError('スタックブランクエラー')

        self.top -= 1
        return self.stack[self.top]

def main():
    expr = sys.stdin.readline().strip().split(' ')
    stack = Stack(100)
    
    for i in expr:
        if i == '*' or i == '+' or i == '-':
            n1 = stack.pop()
            n2 = stack.pop()
            ans = eval(n2 + i + n1)
            stack.push(str(ans))
        else:
            stack.push(i)

    print(stack.pop())
    
if __name__ == '__main__':
    main()

処理内容の割にはかなり大げさなプログラムになってしまいましたが、C言語で書こうとすると、大体このような感じのプログラムになります。

もし、リストオブジェクトの機能を利用するのであれば、以下のような非常に簡単なプログラムになります。

import sys

def main():
    expr = sys.stdin.readline().strip().split(' ')
    stack = []
    
    for i in expr:
        if i == '*' or i == '+' or i == '-':
            n1 = stack.pop()
            n2 = stack.pop()
            ans = eval(n2 + i + n1)
            stack.append(str(ans)) # pushの代わりにappedn()を使う。
        else:
            stack.append(i)

    print(stack.pop())
    
if __name__ == '__main__':
    main()
Pythonプログラミング物語 © 2016 Frontier Theme