概要

いまさらですが逆ポーランドを出力するものを書く。元ネタは改訂第4版 C言語によるはじめてのアルゴリズム入門。

本題

逆ポーランドを出力するためには、数値と演算子の優先度を比較しながらstackに値を一時格納する。逆ポーランドの出力が確定した部分からpolishへ格納していく。

豆知識として、Goは*p++のようなポインタの演算ができないことを知った。また、polish[sp2++]のようにindexでインクリメントを利用することは、インクリメントがコンパイラに式ではなく文として解釈されるためできないことも知った。

以下ソースコード。

package main

import (
    "fmt"
)

var stack [10]string
var polish [10]string

func main() {
    formula := "a+b-c*d/e"
    sp1, sp2 := 0, 0

    // 優先順位テーブル
    pri := map[string]int{
        "a": 3, "b": 3, "c": 3, "d": 3, "e": 3,
        "+": 1, "-": 1, "*": 2, "/": 2, "": -1,
    }

    for _, v := range formula {
        for pri[string([]rune{v})] <= pri[stack[sp1]]{
            popAndPush(&sp1, &sp2)
        }
        sp1++
        stack[sp1] = string([]rune{v})
    }
        // stackにたまっているものをpolishへ
    for sp1 > 0{
        popAndPush(&sp1, &sp2)
    }
    fmt.Println(polish)
}

func popAndPush(sp1 *int, sp2 *int){
    *sp2++
    polish[*sp2] = stack[*sp1]
    *sp1--
}

出力結果