スタック

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 + * +"))

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