逆ポーランド記法とスタック

スタック

• Last In, First Outなデータ構造
• 許される操作はPushとPopとClearだけ

逆ポーランド記法

逆ポーランド記法（ぎゃくポーランドきほう、英語: Reverse Polish Notation, RPN）は、数式やプログラムの記法の一種。演算子を被演算子の後にすることから、後置記法 (Postfix Notation) とも言う。

スタックを配列で実現する

• スタックを宣言するときに長さを与える必要がある

package main

import (
    "fmt"
    "os"
)

const LENGTH = 10

type Stack struct {
    arr []int
    sp  int
}

func (s *Stack) Clear() {
    s.sp = -1
}

func (s *Stack) Push(val int) {
    if s.sp >= len(s.arr) {
        fmt.Printf("ERROR: stack overflow\n")
        os.Exit(1)
    }
    s.sp += 1         // スタックポインタを上げてから
    s.arr[s.sp] = val // プッシュ
}

func (s *Stack) Pop() int {
    if s.sp <= -1 {
        fmt.Printf("ERROR: stack underflow\n")
        os.Exit(1)
    }
    ret := s.arr[s.sp] // ポップしてから
    s.sp -= 1          // スタックポインタを下げる
    return ret
}

func NewStack(length int) *Stack {
    if length <= 0 {
        fmt.Println("ERROR: length of array should be more than zero")
        os.Exit(1)
    }
    return &Stack{
        arr: make([]int, length),
        sp: -1,
    }
}

func main() {
    input := make([]int, LENGTH)
    for i, _ := range input {
        input[i] = i
    }
    fmt.Println("Input: ", input)
    s := NewStack(LENGTH)
    for ele := range input {
        s.Push(ele)
    }
    for i := 0; i < LENGTH; i++ {
        fmt.Println("Pop: ", s.Pop())
    }
}

スタックをリストで実現する

• スタックを宣言するときに長さが不要

package main

import (
    "fmt"
    "os"
)

type Cell struct {
    val int
    prev *Cell
    next *Cell
}

type Stack struct {
    sp *Cell
}

func (s *Stack) Clear() {
    s.sp = nil
}

func (s *Stack) Pop() int {
    if s.sp == nil {
        fmt.Println("ERROR: no value in stack")
        os.Exit(1)
    }
    ret := s.sp.val
    s.sp = s.sp.prev
    return ret
}

func (s *Stack) Push(val int) {
    fmt.Println("PUSH: ", val)
    c := NewCell(val)
    if s.sp == nil {
        s.sp = c
        return
    }
    s.sp.next = c
    c.prev = s.sp
    s.sp = c
}

func NewCell(val int) *Cell {
    return &Cell{val: val, prev: nil, next: nil}
}

func NewStack() *Stack {
    return &Stack{sp: nil}
}

func main() {
    s := NewStack()
    s.Push(3)
    s.Push(4)
    s.Push(5)
    fmt.Println("Pop: ", s.Pop())
    fmt.Println("Pop: ", s.Pop())
    fmt.Println("Pop: ", s.Pop())
}

逆ポーランド記法で書かれた式をスタックを用いて評価する

package main

import (
    "fmt"
    "os"
    "strconv"
    "strings"
)

type Stack struct {
    arr []int
    sp  int
}

func (s *Stack) Clear() {
    s.sp = -1
}

func (s *Stack) Push(val int) {
    if s.sp >= len(s.arr) {
        fmt.Printf("ERROR: stack overflow\n")
        os.Exit(1)
    }
    s.sp += 1         // スタックポインタを上げてから
    s.arr[s.sp] = val // プッシュ
}

func (s *Stack) Pop() int {
    if s.sp <= -1 {
        fmt.Printf("ERROR: stack underflow\n")
        os.Exit(1)
    }
    ret := s.arr[s.sp] // ポップしてから
    s.sp -= 1          // スタックポインタを下げる
    return ret
}

func NewStack(length int) *Stack {
    if length <= 0 {
        fmt.Println("ERROR: length of array should be more than zero")
        os.Exit(1)
    }
    return &Stack{
        arr: make([]int, length),
        sp: -1,
    }
}

func main() {
    target := "2 1 + 3 *"
    input := strings.Split(target, " ")
    s := NewStack(len(input) + 1)
    for _, ele := range input {
        switch ele {
        case "+":
            right := s.Pop()
            left := s.Pop()
            s.Push(left + right)
        case "-":
            right := s.Pop()
            left := s.Pop()
            s.Push(left - right)
        case "*":
            right := s.Pop()
            left := s.Pop()
            s.Push(left * right)
        case "/":
            right := s.Pop()
            left := s.Pop()
            s.Push(left / right)
        default:
            s.Push(atoi(ele))
        }
    }
    fmt.Println(target, " = ", s.Pop())

}

func atoi(a string) int {
    ret, _ := strconv.Atoi(a)
    return ret
}

ops = {
  "+": (lambda a, b: a + b),
  "-": (lambda a, b: a - b),
  "*": (lambda a, b: a * b),
  "/": (lambda a, b: a / b)
}

def eval(expression):
  tokens = expression.split()
  stack = []

  for token in tokens:
    if token in ops:
      arg2 = stack.pop()
      arg1 = stack.pop()
      result = ops[token](arg1, arg2)
      stack.append(result)
    else:
      stack.append(int(token))

  return stack.pop()

print(eval("1 2 + "))
print(eval("990 1 2 + *"))
print(eval("1000 990 1 2 + * +"))

暇なときに普通の式を逆ポーランド記法にコンパイルするプログラムを書く。